# 점화식

둘러보기로 가기 검색하러 가기

## 개요

• 점화식 : 수열의 여러항들이 만족시키는 관계
• 점화식이 만족하는 수열의 일반항을 알아 내는 문제 등
• 보통의 경우 초기항이 주어져야 완전한 답을 낼 수 있다.

## 기본적인 점화식

• $$a_{n+1} - a_n = c$$ : 등차수열
• $$a_{n+1} / a_n = c$$ : 등비수열
• $$a_{n+1} - a_n = b_n$$ : 계차수열 참고.
• $$a_{n+1} / a_n = b_n$$ : 계차수열을 통한 풀이에서, <모든 항을 더하>지 않고 <모든 항을 곱하>면 됨.

## 기본 점화식의 응용

• $$a_{n+1} = ka_n + c$$
• 양변에 적당한 상수를 더하면 $$(a_{n+1} + p)= k(a_n + p)$$ 꼴로 만들 수 있다.
• 일반항이 $$(a_n + p)$$ 인 수열은 공비 $$k$$ 인 등비수열, $$a_n + p =(a_1 + p) k^{n-1}$$
• 적당한 상수 $$p$$ 는 어떻게 찾냐고? 생각해 볼 것.
• ex) $$a_{n+1} = 2a_{n} + 3$$, 초기항 1 양변에 3을 더하면 $$(a_{n+1} +3 )= 2( a_{n} + 3)$$, 적당한 상수 $$k$$ 에 대하여 $$a_{n} + 3 = k 2^n$$ 초항을 만족시키는 $$k$$ 값은 2이므로, $$a_n = 2^{n+1} - 3$$

• $$a_{n+1} = ra_n + b_n$$ 꼴의 점화식
• 양변을 $$r^{n+1}$$ 로 나눈 후, $$a_n / r^n$$ 에 대한 점화식을 푸는 것이 한 방법. $$b_n$$ 이 등비수열인 경우 효과적이다.
• 양변에 적당히 $$n$$ 에 대한 식을 더해서 공비 $$r$$ 에 대한 등비수열 꼴로 만들 수 있는 경우가 많다.
• $$b_n$$ 이 다항식인 경우, 양변에 $$b_n$$ 과 같은 차수의 다항식을 (계수를 문자로 두고) 더해서, 등비수열 꼴로 만든 후에 계수 비교를 통해 문자를 찾는다.
• ex ) $$a_{n+1} = 2a_n + 3n + 5$$ 인 경우, 양변에 $$pn + q$$ 를 더하면$a_{n+1} + pn + q = 2a_n + (3+p)n + (5+q)$ 우변이 $$2(a_n+ pn + q)$$ 인 경우에 등비수열이 되니까, $$3+p = 2p, \quad 5+q=2q$$ 이므로 $$p=3, \quad q=5$$. 그러므로$a_n + 3n + 5 = k2^n$. 초기항이 주어진 경우 k 를 찾을 수 있다.

• 점화식에 덧셈 기호가 없을 때
• 로그를 취하면 도움이 됨. 로그의 밑은 계산이 간단하도록 적절히 선택하기.
• ex) $$a_{n+1} = 4a_n^2$$ : 밑 2 인 로그를 취하면 $$\log a_{n+1} = 2\log a_n + 2$$ 이제 $$\log a_n = b_n$$에 대한 점화식을 풀면 됨. (양변에 2를 더해서 …)
• 점화식이 분수꼴일때
• 역수를 취하면 도움이 될 때가 많음. (만능은 아님)
• ex) $${a_{n+1}} = \frac{2a_n}{3a_n+1}$$ : 역수를 취하면 $$\frac{1}{a_{n+1}} = \frac{1}{2} \frac{1}{a_n} + \frac{3}{2}$$. 이제 $$b_n = \frac{1}{a_n}$$ 에 대한 점화식으로 보고 풀면 됨.
• 점화식에 $$a_n$$ 과 $$S_n$$ 이 함께 나올 때
• $$S_n - S_{n-1}=a_n$$$$(n \ge 2)$$ , $$S_1 = a_1$$ 의 관계를 사용하면 $$a_n$$ 만의 점화식으로 만들 수 있다.
• ex) $$a_n = 2 S_n + 3^n$$ 일 때, $$a_1 = 2 a_1 + 3$$ 이므로 $$a_1 = -3$$$a_{n+1} = 2 S_{n+1} + 3^{n+1}$ 식과 $$a_n = 2 S_n + 3^n$$ 식을 빼 주면 $$a_{n+1} - a_n = 2 a_{n+1} + 2\cdot 3^{n}$$ 이제부터는 알아서 할 것. 부분합과 일반항이 함께 등장하는 점화식에서는 초기 조건에서 실수를 할 가능성이 높으므로, $$a_1, a_2, a_3$$ 정도는 점화식으로부터 직접 구해 보는 것이 좋을 것이다. 그리고 구한 일반항 $$a_n$$ 은 $$(n \ge 2)$$ 에서만 성립하는 식일 가능성도 있다.

## 선형점화식

• $$pa_{n+2} + qa_{n+1} + ra_n = 0$$ 꼴의 점화식
• $$pa_{n+2} + qa_{n+1} + ra_n = b_n$$ 꼴의 점화식
• 상수계수 선형점화식 항목을 참조

## 노트

### 말뭉치

1. The procedure for finding the terms of a sequence in a recursive manner is called recurrence relation.[1]
2. We study the theory of linear recurrence relations and their solutions.[1]
3. Doing so is called solving a recurrence relation .[2]
4. Recall that the recurrence relation is a recursive definition without the initial conditions.[2]
5. , 485\ldots\text{.}\) Solution Finding the recurrence relation would be easier if we had some context for the problem (like the Tower of Hanoi, for example).[2]
6. Remember, the recurrence relation tells you how to get from previous terms to future terms.[2]
7. Recurrence relations are used to reduce complicated problems to an iterative process based on simpler versions of the problem.[3]
8. Identifying a candidate problem to solve with a recurrence relation: The problem can be reduced to simpler cases.[3]
9. The term difference equation sometimes (and for the purposes of this article) refers to a specific type of recurrence relation.[4]
10. A recurrence relation is an equation that expresses each element of a sequence as a function of the preceding ones.[4]
11. This defines recurrence relation of first order.[4]
12. The recurrence of order two satisfied by the Fibonacci numbers is the archetype of a homogeneous linear recurrence relation with constant coefficients (see below).[4]
13. In this article, we will see how we can solve different types of recurrence relations using different approaches.[5]
14. Therefore, we need to convert the recurrence relation into appropriate form before solving.[5]
15. There are a variety of methods for solving recurrence relations, with various advantages and disadvantages in particular cases.[6]
16. One method that works for some recurrence relations involves generating functions.[6]
17. If we can find an explicit representation for the series for this function, we will have solved the recurrence relation.[6]
18. We can often solve a recurrence relation in a manner analogous to solving a differential equations by multiplying by an integrating factor and then integrating.[7]
19. Wolfram|Alpha can solve various kinds of recurrences, find asymptotic bounds and find recurrence relations satisfied by given sequences.[8]
20. This is called a recurrence relation.[9]
21. We somehow need to figure out how often the first versus the second branch of this recurrence relation will be taken.[9]
22. We will first find a recurrence relation for the execution time.[9]
23. These recurrence relations are shown to be closely related to each other.[10]
24. Racah has obtained a recurrence relation for the inner multiplicity (multiplicity of weights).[10]
25. Moreover, Kostant's recurrence relation for the partition function as well as Racah's recurrence relation for the inner multiplicity have been generalized.[10]
26. In this paper, the recurrence relation for negative moments along with negative factorial moments of some discrete distributions can be obtained.[11]
27. Is D(4) easier to calculate using the factorial formula or using the recurrence relation?[12]
28. Therefore the solution to the recurrence relation will have the form: a n =a2n+b18n.[13]
29. Therefore the solution to the recurrence relation will have the form: a n =a.6n+b.n.6n.[13]
30. Explanation: Check for the left side of the equation with all the options into the recurrence relation.[13]
31. Together with the initial conditions, the recurrence relation provides a recursive definition for the elements of the sequence.[14]
32. The solution techniques for these two classes of recurrence relation are discussed in detail in the Recurrence page.[15]
33. We also justified Pascal's Formula as a recurrence relation.[16]
34. Let's write a recurrence relation for the sum of the elements in column 1 of the triangle.[16]
35. Write a recurrence relation H(n) to describe the number of moves required when the left tower has n rings on it.[16]
36. Write a recurrence relation b(n) to describe the balance due on the loan after n payments.[16]
37. A recurrence relation is an equation which represents a sequence based on some rule.[17]
38. Once the values of a 0 and a 1 are specified, the whole sequence {a i } i 0 is completely specified by the recurrence relation.[18]
39. Observe that the difference of the highest index (n+1) and the lowest index (n-2) is exactly the order 6 of the recurrence relation.[18]
40. Since the highest index in the recurrence relation is n+1 while the lowest index is n-2, their difference (n+1)-(n-2)=3 must be the order m, i.e. m=3.[18]
41. For each fixed m, these two generating functions share the same denominator, hence the same recurrence relation .[19]
42. After studying it carefully, it is found that the solutions cannot be given exactly due to the complicated three-term recurrence relation .[19]
43. Recurrence relations can also be used to calculate some sequences that are usually computed nonrecursively , e.g. via a closed-form formula .[20]
44. Of course recurrence relations are not limited in application to sequences of integers.[20]

## 메타데이터

### Spacy 패턴 목록

• [{'LOWER': 'recurrence'}, {'LEMMA': 'relation'}]
• [{'LOWER': 'recurrent'}, {'LEMMA': 'sequence'}]