How to solve this by using the generating functions? What is the possible solution for this?
recurrence relation $$ a_n = 5a_{n-1} – 6a_{n-2}, n \ge 2,\text{ given }a_0 = 1, a_1 = 4.$$
Thanks.
[Math] recurrence relation, linear, second order, homogeneous, constant coefficients, generating functions
recurrence-relations
Best Answer
So that you can begin to see connections, we look at the same problem using generating functions. The details look somewhat harder than the characteristic equation method. In fact the procedure is quite mechanical, and is abstractly the same as the characteristic equation method.
Let $$f(t)=a_0+a_1t+a_2t^2+a_3t^3+ \cdots + a_nt^n+ \cdots. \qquad\qquad(\ast)$$ Note that we are looking at $(\ast)$ as a formal power series, as simply a carrier for the coefficients. (In fact it does converge if $|t|<1/3$.) We have $$5tf(t)=5a_0t+5a_1t^2+5a_2t^3+\cdots +5a_{n-1}t^n+\cdots,$$ $$6t^2f(t)=6a_0t^2+6a_1t^3+6a_2t^4+\cdots+6a_{n-2}t^n+\cdots.$$ Let $g(t)=f(t)-5tf(t)+6t^2f(t)$. Note that for $n \ge 2$, the coefficient of $t^n$ is equal to $a_n-5a_{n-1}+6a_{n-2}$, which is $0$. So $g(t)=a_0+a_1t-5a_0t$. Since $a_0=1$ and $a_1=4$, we have $g(t)=1-t$, and therefore $$f(t)=\frac{1-t}{1-5t+6t^2}.$$ Using the partial fractions procedure, which is not simply an integration trick, we find that $$f(t)=\frac{-1}{1-2t} +\frac{2}{1-3t}.$$ But the power series expansions of $\frac{1}{1-2t}$ and $\frac{1}{1-3t}$ are easy to write down, since $\frac{1}{1-x}=1+x+x^2+\cdots$. We conclude that the coefficient of $t^n$ in the expansion of $f(t)$ is given by $$a_n=-(2^n)+2(3^n).$$