상수계수 선형점화식

개요

• 선형점화식은 선형 미분방정식의 이론과 유사한 점이 많다
• 선형대수학의 도구들을 사용할 수 있다
  • 점화식, 미분방정식, 선형대수학 항목 참조

 

이계 상수계수 선형점화식

• \(pa_{n+2} + qa_{n+1} + ra_n = 0\) 꼴의 점화식
  
  • \(p+q+r =0\) 일 때
    
    • 잘 정리하면 \(a_{n+2} - a_{n+1} = r(a_{n+1} - a_n)\) 의 형태로 만들 수 있다. 그러면 계차수열 \(b_n = a_{n+1} - a_{n}\) 에 대한 등차수열이라고 생각하고, \(b_n\) 을 구한다.
    • 계차수열을 알 때 일반항을 구하는 건 할 수 있지?
  • \(p+q+r \ne 0 \) 일 때 : (교육 과정 외, 이 점화식만은 외우는 것을 권장함. 유도 과정이 너무 길다.)
    
    • 결론부터 말하자면,
      
      • \(px^2 + qx + r = 0 \) 의 두 근을 \(\alpha, \beta\) 라 하면, \(a_n = A\alpha^{n-1} + B\beta^{n-1}\) 꼴이며, 초기항 두 개를 아는 경우 상수를 찾을 수 있다.
      • 중근 \(\alpha\) 를 가지는 경우에는 \(a_n = A\alpha^{n-1} + Bn\alpha^{n-1}\) 꼴이 된다.
    • \(px^2 + qx + r = 0 \) 의 두 근 \(\alpha, \beta\) 에 대하여, \(p(\alpha+ \beta) = -q,\quad p(\alpha \beta) = r\) 이다. (근과 계수와의 관계) 그러므로\[a_{n+2} - (\alpha + \beta)a_{n+1} + \alpha \beta a_n = 0\] 라고 쓸 수 있다.
      이제 \(a_{n+2} - \alpha a_{n+1} = \beta(a_{n+1} -\alpha a_n)\) 으로 쓸 수 있다. \((a_{n+1} -\beta a_n)\) 에 대한 등비수열을 풀기.\[a_{n+2} - \beta a_{n+1} = \alpha (a_{n+1} -\beta a_n)\] 로도 쓸 수 있다. \((a_{n+1} -\alpha a_n)\) 에 대한 등비수열을 풀기.
      연립해서 \(a_{n+1}\) 을 소거하면 끝! 중근을 가지는 경우에 대한 유도는 독자에게 맡긴다.
      이 점화식을 \(p+q+r=0\) 인 점화식에 적용해서 풀지 말라는 법도 없다. 한 근이 무조건 1 이 나와서, (등비수열) + (상수) 꼴의 일반항이 나온다.
      
    • ex) 피보나치 수열 \(a_{n+2} = a_{n+1} + a_n\) 의 일반항을 구하시오. (\(a_1 = a_ 2 = 1\))
• \(pa_{n+2} + qa_{n+1} + ra_n = b_n\) 꼴의 점화식
  
  • 양변에 적당히 \(n\) 에 대한 식을 더해서 공비 \(r\) 에 대한 등비수열 꼴로 만들 수 있는 경우가 많다.

 

 

관련된 항목들

• 선형점화식과 점근 급수
• 점화식
• 상수계수 이계 선형미분방정식
• 점화식, 미분방정식, 선형대수학

리뷰논문, 에세이, 강의노트

• Speyer, Linear Recurrences and Rational Generating Functions
• Some properties of holonomic sequences