Showing that a series solves a recurrence relation

Question

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.

Answer 1

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$.

Answer 2

$$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}}.$

Answer 3

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.