점화식

개요

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

기본적인 점화식

• \(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\) 꼴의 점화식
• 상수계수 선형점화식 항목을 참조

관련된 항목들

• 차분방정식
• 선형대수학

사전 형태의 자료

• http://ko.wikipedia.org/wiki/점화식
• http://en.wikipedia.org/wiki/Recurrence_relation

메타데이터

위키데이터

• ID : Q740970

노트

말뭉치

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

메타데이터

위키데이터

• ID : Q740970

Spacy 패턴 목록

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