# Showing that a series solves a recurrence relation

Let: $$a_n = a_{n-1}+2a_{n-2} +3\cdot 2^n$$, $$\displaystyle b_n=4\sum_{k=0}^nk\binom n k$$

Show that $$b_n$$ solves $$a_n$$

There are no starting conditions for the recurrence, that is how the question was given.

I don't understand, how can it be done? I can't solve the recurrence since there are no starting conditions, I can find a generating function for $$b_n$$ but I don't see how that will help.

• What does it mean that a sequence solves another one? To check that $b_n-b_{n-1}-2b_{n-2}=3\cdot 2^n$ we just need induction. Jun 22, 2015 at 19:18
• I don't think I know what does it mean... @JackD'Aurizio Jun 22, 2015 at 19:19
• Just plug in the sum into the recurrence and check that the equality works. Jun 22, 2015 at 19:24

Simply plug in the quantity $b_n$ in for $a_n$.

We wish to show the following:

$$b_n = b_{n-1} + 2b_{n-2} +3 \times 2^n$$

This will be sufficient to prove the recurrence stated.

The reason initial conditions don't matter is because you are trying to show that the $b_n$ described are A SOLUTION for the recurrence given, not a unique solution.

A hint to go about this is to rewrite $b_n$ in a more compact format. Notice that the formula for $b_n$ gives the number of ways to pick a subset of $n$ elements and picking a special element of that subset, multiplied by $4$. This is the same as picking a special element initially and deciding whether or not each of the remaining $n-1$ elements should be in your subset, multiplied by 4.

Notice therefore that we have $b_n = 4 (n2^{n-1}) = n 2^{n+1}$. From there simple algebra should get you your recurrence.

Another way to show that $b_n$ satisfies the recurrence is to find a combinatorial meaning of $b_n$ and show it implies the given recurrence for $b_n$.

$$b_n = 4\sum_{k=0}^{n}\binom{n}{k}k = 4\frac{d}{dx}\left.\sum_{k=0}^{n}\binom{n}{k}x^k\right|_{x=1}=4\frac{d}{dx}\left.(1+x)^n\right|_{x=1}= n 2^{n+1}$$ and now it is straightforward to check that $b_n - b_{n-1}-2b_{n-2}=3\cdot 2^{n\color{red}{-1}}.$

• Derivative?! say whaaaat?! Jun 22, 2015 at 19:37
• @kuhaku: welcome to the astonishing world of analytic combinatorics. Jun 22, 2015 at 20:18

You want to show that if

$$t_n = 4\sum_{k=0}^n k \binom n k \tag{P1}$$

Then

$$t_n = t_{n-1} + 2t_{n-2} +3\cdot 2^n \tag{P2}$$

You want to show $\text{P1} \implies \text{P2}$, so you don't need initial conditions. If you were trying to show $\text{P2} \implies \text{P1}$, then you would need initial conditions.

So if $\text{P1}$ holds, then the following is true:

$$t_{n} = 4\sum_{k=0}^{n} k \binom{n}k$$ $$t_{n-1} = 4\sum_{k=0}^{n-1} k \binom{n-1}k$$ $$t_{n-2} = 4\sum_{k=0}^{n-2} k \binom{n-2}k$$

So, then the question is, does the following hold? :

$$4\sum_{k=0}^{n} k \binom{n}k = 4\sum_{k=0}^{n-1} k \binom{n-1}k + 2 \cdot 4\sum_{k=0}^{n-2} k \binom{n-2}k +3\cdot 2^n \tag{P3}$$

If you know that

$$\sum_{k=0}^n k {n \choose k} = n~2^{n-1}$$

then it is easier to work out.

An alternative approach is to show that $\text{P2}$ is equivalent to $\text{P4}$ by the following:

$$t_n = t_{n-1} + 2t_{n-2} + 3\cdot 2^n$$ $$t_{n + 1} = t_{n} + 2t_{n - 1} + 6\cdot 2^n$$

Cancel out the $2^n$ between the equations, so

$$t_{n+1} = 3~t_{n} - 4~t_{n-2} \tag{P4}$$

So you can use this easier form to work out the problem.