Linear Nonhomogeneous Recurrence Relations

Question

I have to find a formula for the recurrence $a_{n+1}=2a_n + 2^n$ with $a_0 = 3$. I've started to solving its associated equation $a_{n+1}=2a_n$ and I've found the solution $a_n =\alpha 2^n$. Then I know that a trial solution for the nonhomogeneous recurrence could be $C2^n$ (with C costant). Now, the equation becomes $C2^{n+1} = 2C2^n + 2^n \iff 0 =2^n$. I don't understand where I've made the mistake...

Answer 1

Hint:

Try rather $a_n = \alpha 2^n + \beta$ because of the non-linear aspect and solve for $\beta$ first using recurrence, then for $\alpha$ using $a_0$. Your attempt shows that $\alpha 2^n$ is not solution.

A non-trial approach:

When encountering such non-linear relations, one can attempt to linearize them, for example, let be $b_n = a_{n + 1} - 2a_n = 2^n$.

Then $b_{n + 1} = 2 b_n$ by construction.

Then : $a_{n + 2} - 2a_{n + 1} = 2(a_{n + 1} - 2a_n)$.

Then : $a_{n + 1} = 4a_{n + 1} - 4 a_n \qquad (*)$.

$(*)$ is a linear relation between sequences.

Using well-known formulas, we can conclude $a_n = (\alpha n + \beta) 2^n$ because $x^2 - 4x + 4 = (x - 2)^2$.

Finally, $a_0 = 3$ and $a_1 = 7$, then $\alpha = \dfrac{1}{2}$ and $\beta = 3$.

So that $a_n = 3 \times 2^n + n 2^{n - 1}$.

Answer 2

Dividing $\;a_{n+1}=2a_n + 2^n\;$ by $\,2^{n+1}\,$ gives $\;\dfrac{a_{n+1}}{2^{n+1}} = \dfrac{a_n}{2^n}+\dfrac{1}{2}\,$, so $\,\dfrac{a_n}{2^n}\,$ is an arithmetic progression with common difference $\,\dfrac{1}{2}\,$, and therefore $\;\dfrac{a_n}{2^n} = \dfrac{a_0}{2^0}+ n \cdot \dfrac{1}{2} = \dfrac{n+6}{2}\iff a_n = 2^{n-1}(n+6)\,$.