계수가 일정하지 않은 반복 관계에 대한 닫힌 공식 찾기

Nov 17 2020

우리는 재귀 관계에 대한 닫힌 공식을 작성하는 것을 알고 있습니다.

만약 $a_n=7a_{n-2}+6a_{n-3} $$a_0=9,a_1=10,a_2=32 $ , 닫힌 공식은 다음과 같습니다.

$a_n=8(-1)^{n}+4(3)^{n}+(-3)(-2)^{n}$. (여기에 모든 프로세스를 작성할 필요는 없습니다.)

내 질문은 계수가 다음과 같은 변수라면 어떻게 될까요? $(n-1) ,(n) $ 대신에 $6,7$.

계수가 일정하지 않은 순환 관계의 닫힌 공식을 찾는 절차가 있습니까?

예를 들면; 재귀가 다음과 같은 경우$a_n=(n-1)a_{n-2}+na_{n-3} $$a_0=9,a_1=10,a_2=32 $ , 닫힌 공식은 무엇입니까?

답변

2 HallaSurvivor Nov 17 2020 at 03:34

이 경우에 다른 프로세스가 다르게 일반화되므로 어떤 프로세스를 사용했는지 잘 모르겠습니다. 나는 개인적으로 함수 생성에 부분적 이므로 그 방법에 대해 논의 할 것입니다.

중요한 관찰은 계수가 $(n-1)a_{n-2}$많이 파생 상품 등이. 결국 우리가

$$A = \sum a_n x^n$$

그때 $$\frac{d}{dx} A = \sum n a_n x^{n-1}$$.

당신이 포즈를 취한 예에서 $a_n = (n-1)a_{n-2} + na_{n-3}$, 우리는 보이는 모든 것을 다음과 같이 곱할 수 있습니다. $x^n$ 그리고 얻을 합계

$$A = \sum a_n x^n = \sum \left ( (n-1) a_{n-2} x^n + n a_{n-3} x^n \right )$$

오른쪽을 다음과 같이 분할했습니다.

$$x^2 \sum (n-1) a_{n-2} x^{n-2} + x^3 \sum n a_{n-3} x^{n-3}$$

이제 미분 규칙을 사용하여이를 단순화하여 다음에 대한 미분 방정식을 얻을 수 있습니다. $A$. 그런 다음 미분 방정식을 풀면 닫힌 형식을 얻을 수 있습니다.$A$. 이 모든 것은 sage 와 같은 컴퓨터 대수 시스템에서 자동화 될 수 있지만 , 약간의 지속성을 가지고 손으로 할 수 있습니다.

이 기술에 대한 자세한 내용은 Wilf의 환상적인 책 생성 기능론에서 읽을 수 있습니다 .


도움이 되었으면 좋겠습니다 ^ _ ^