Generating functions (index shifting) 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!
 A: 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.
A: 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.
A: 
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}.$$
