Solving $a_n = 5a_{n-1} + 6a_{n-2}$

188 Views Asked by At

Translation: Find a closed form solution to the recurrence relation $ a_n = 5a_{n-1} + 6a_{n-2}$ with $a_1 = 1$ and $a_2 = 2$.


Original: Determine a forma fechada da relação de recorrência com primeiro e segundo termos, respectivamente 1 e 2 , e A(n)=5a(n-1) - 6A(n-2).

1

There are 1 best solutions below

0
On

We can do this with a generating function, but it will be easier to first do some re-indexing. Instead of $a_1=1, a_2=2$, let us write $a_0=1, a_1=2$, and instead of writing $a_n=5a_{n-1}+6a_{n-2}$, let us write $a_{n+1}=5a_{n}+6a_{n-1}$.

Define $$A(x)= \sum_{n\ge 0}^{}a_{n}x^{n} = a_0+a_1x+a_2x^2+a_3x^3...$$ to be our generating function. The $a_{i}$'s are obviously the $i^{th}$ terms of the recurrence.

Take our recurrence relation $a_{n+1}=5a_{n}+6a_{n-1}$ and multiply it by $x^{n}$, and then sum everything over the valid values of $n$ (which, because the first term is $a_0$, are all $n\ge1$). Working with the left side first, we get: $$\sum_{n\ge 1}^{}a_{n+1}x^{n} = a_2x+a_3x^2+a_4x^3...$$Which is equal to: $$(A(x)-2x-1)/x$$

In other words, the above series was obtained from $A(x)$ by first subtracting the $a_0$ and the $a_1x$ terms, then dividing the remaining terms by x. Substituting the values for $a_0$ and $a_1$ results in the subtraction seen in the numerator of the fraction.

Now let's do it on the right: $$\sum_{n\ge 1}^{}x^{n}(5a_{n}+6a_{n-1}) = \sum_{n\ge 1}^{}5a_{n}x^{n}+\sum_{n\ge 1}^{}6a_{n-1}x^{n}=5\sum_{n\ge 1}^{}a_{n}x^{n}+6\sum_{n\ge 1}^{}a_{n-1}x^{n}$$

The first sum is really easy: it's just $A(x)$ minus the $a_0$ term, which is $1$; overall, this sum is equal to $5(A(x)-1)=5A(x)-5$.

Now for the second sum. Ignore the $6$ for now and write out the first few terms: $\sum_{n\ge 1}^{}a_{n-1}x^n=a_0x+a_1x^2+a_2x^3...$, which is pretty clearly equal to $xA(x)$. Multiply by the $6$ out front and we end up with $6xA(x)$.

Great! We now have all we need to find what we want, $A(x)$ — we simply need to solve for it. Set up the appropriate equation and go through the algebra:

$$\frac{A(x)-2x-1}{x}=5A(x)-5+6xA(x) = A(x)(6x+5)-5$$

$$A(x)-2x-1=A(x)(6x^2+5x)-5x$$

$$A(x)-A(x)(6x^2+5x)=1-3x$$

$$A(x)(1-5x-6x^2)=1-3x$$

$$A(x) = \frac{1-3x}{1-5x-6x^2}$$

Believe it or not, that's it! Were you to expand this as a power series, you would find $a_n$ to be the coefficient of $x^n$ of the expansion — which was the goal, and illustrates the elegance of this representation; every single term of the recurrence is contained in this one single expression! Considering that there are infinitely many terms altogether, that's pretty damned mindblowing, don't you think?