Generating functions (index shifting)

Question

I am going through old exam questions for my upcoming exam, but got stuck on a question since I don't really understand the solution.

The question I have a problem with (in boldface):

(b) Let the sequence $a_n$ be given by the recurrence relation $$a_{n+2} =2a_{n+1} +a_n, \qquad a_1=1, a_2=3.$$ (i) Calculate $a_3$, $a_4$ and $a_5$.

(ii) Prove that the generating function for the sequence is $$\boldsymbol{ A(x) =\sum_{n=1}^\infty a_n x^n = \dfrac{x+x^2}{1-2x-x^2}.}$$

and the solution:

(ii) Multiply each side of the recurrence by $x^{n+2}$ and sum over $n$ to get $$\sum_{n=1}^\infty a_{n+2} x^{n+2} =2 \sum_{n=1}^\infty a_{n+1} x^{n+2} +\sum_{n=1}^\infty a_n x^{n+2}.$$ Change summation index $$\sum_{n=2}^\infty a_{n} x^{n} =2x \sum_{n=1}^\infty a_{n} x^{n} +x^2 \sum_{n=0}^\infty a_n x^{n}.$$ Add/subtract missing terms $$A(x) -a_1 x -a_2 x^2 =2x(A(x)-a_1 x) +x^2 A(x)\\ \implies \quad A(x)-x-3x^2 =2x(A(x)-x) +x^2A(x)\\ \implies \quad A(x) (1-2x-x^2) =x +3x^2 -2x^2 =x +x^2\\ \implies \quad A(x) =\dfrac{x+x^2}{1-2x-x^2}.$$

My problem is that I can't wrap my head around how the index-shifting works. I think the first summation (after the index-shifting) should start from $n=3$, since it seems like they set $k = n+2$. I'd be really thankful if someone could explain how it works. I understand everything else. Thank you!

Answer 1

Yes, you are right, after the "change summation index", we shoud have $$\sum_{n=3}^\infty a_{n} x^{n} =2x \sum_{n=2}^\infty a_{n} x^{n} +x^2 \sum_{n=1}^\infty a_n x^{n}.$$ that is $$A(x)−a_1x−a_2x^2=2x(A(x)−a_1x)+x^2A(x)$$ where $A(x)=\sum_{n=1}^\infty a_n x^{n}$. The rest of the proof is correct.

Answer 2

I think the first summation (after the index-shifting) should start from $n=3$, since it seems like they set $k=n+2$.

You are right indeed, since $$\sum_{n=1}^\infty a_{n+2} x^{n+2} =a_3 x^3 +a_4 x^4 +a_5 x^5 +\ldots =\sum_{n=3}^\infty a_n x^n.$$ Also, note that the third summation in the second step should start from $n=1$: $$\sum_{n=1}^\infty a_{n} x^{n+2} =x^2 \sum_{n=1}^\infty a_{n} x^{n}.$$

Answer 3

You already have some excellent answers, but I would like to take this opportunity to demonstrate a little trick which I think simplifies the solution a little.

First, write the recurrence in the form $$a_n = 2a_{n-1}+a_{n-2}$$ valid for all $n \ge 2$, with $a_1=1$ and $a_2=3$. The trick is to alter the equation so that it is valid for all $n \ge 0$, using the Kronecker delta function: $$a_n = 2a_{n-1}+a_{n-2} + \delta_{1n} + \delta_{2n}$$ The method for determining the deltas is to first adjust the equation so it holds for $n=1$, and then apply another adjustment for $n=2$. This is where we use the initial conditions $a_1=1$ and $a_2=3$. It turned out in this problem that the deltas all have a coefficient of $1$, but this is not the case in general.

Now multiply by $x^n$ $$a_n x^n= 2a_{n-1}x^n+a_{n-2}x^n + \delta_{1n}x^n + \delta_{2n}x^n$$ and sum over all $n \ge 0$ $$\sum_{n=0}^{\infty} a_n x^n= \sum_{n=0}^{\infty}2a_{n-1}x^n+\sum_{n=0}^{\infty}a_{n-2}x^n + x + x^2$$ so $$A(x) = 2xA(x) + x^2 A(x) +x+x^2$$ which we can then solve for $A(x)$, as before.

I learned this trick from an online video by Robert Sedgewick, co-author of An Introduction to the Analysis of Algorithms and Analytic Combinatorics. Curiously, I don't think he demonstrates the trick in those books.