Find generating function of series $a_{n} = 2^{n} + 3^{n} $

Question

Find generating function of series $a_{n} = 2^{n} + 3^{n} $

I'm having a problem with this because at first i have to find recursive equation for $a_{n}$ . I find that $a_{0} = 2$ , $a_{1} = 5$ but how do I find the rest? Also I can't simply add generating functions, I have to solve recursive equation using generating functions. First step is to find recursive equation for $a_{n}$ then some other stuff that I can handle.

Answer 1

$$a_n=2^n+3^n,\\ a_{n+1}=2\cdot2^n+3\cdot3^n,\\ a_{n+2}=4\cdot2^n+9\cdot3^n$$

Then we eliminate $2^n$ and $3^n$ from the above relations by

$$a_{n+2}-4a_n=5\cdot3^n,\\ a_{n+1}-2a_n=3^n$$

and

$$a_{n+2}-4a_n=5(a_{n+1}-2a_n)$$

or

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

---

You can reach the same conclusion by noting that the characteristic polynomial has roots $2$ and $3$, hence is $$r^2-5r+6,$$ corresponding to the recurrence

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

Answer 2

Hint: What are the roots of the characteristic equation of that recursive relation?

Answer 3

Hint:

$$\sum_{n=0}^\infty a_nx^n = \sum_{n=0}^\infty (2^n+5^n)x^n = \sum_{n=0}^\infty (2x)^n + \sum_{n=0}^\infty (5x)^n = \frac1{1-2x} + \frac1{1-5x}$$

---

Now you can proceed to find the recursive relation:

$$\sum_{n=0}^\infty a_nx^n = \frac1{1-2x} + \frac1{1-5x} = \frac{2-7x}{1-7x+10x^2}$$

$$\sum_{n=0}^\infty a_nx^n - 7\sum_{n=1}^\infty a_{n-1}x^n + 10 \sum_{n=2}^\infty a_{n-2}x^n = (1-7x+10x^2)\sum_{n=0}^\infty a_nx^n = 2-7x$$

Comparing powers gives:

\begin{align} x^0:& \quad a_0 =2\\ x^1:& \quad a_1 - 7a_0 = -7 \implies a_1 = 7\\ x^k \text{ for } k \ge 2:& \quad a_k - 7a_{k-1} + 10a_{k-2} = 0 \end{align}

Answer 4

Looking very closely at the terms one can identify $$a_0=2$$ $$a_1=5=3*a_0-1=3a_0-2^0$$ $$a_2=13=3a_1-2=3a_1-2^1$$ $$a_3=35=3a_2-4=3a_2-2^2$$ $$a_4=97=3a_3-8=3a_3-2^3$$ $$a_5=275=3a_4-16=3a_4-2^4$$

And in general: $$a_{n+1}=3a_n-2^n$$