0

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

user515933
  • 563

2 Answers2

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

Raito
  • 1,890
  • 11
  • 17
  • I've tried $\alpha 2^n + \beta$ instead of $\alpha 2^n$ and I've obtained $\beta = -2^n$ so the formula should be $a_n = -2^n + 2^{n+2}$ but it's wrong – user515933 Feb 01 '18 at 12:32
  • Huh? Why is it wrong? You should simplify your $a_n$ expression. Hint : $2^{n + 2} = 4 \times 2^n$. – Raito Feb 01 '18 at 14:41
  • The final result with simplification is $a_n =3*2^n$ but the number of recurrence found with this formula are wrong... for example if I have to find $a_1$ the recurrence gives me as the result 7 but the formula find 6 as result – user515933 Feb 01 '18 at 15:06
  • @user515933 You're right, sorry. This again shows that $\alpha 2^n + \beta$ cannot be solution, can you try: $a_n = \alpha 2^n + \beta n + \gamma$ ? (try to use more equations to solve for $\beta, \gamma$) – Raito Feb 01 '18 at 15:25
  • @user515933 Added an alternative proof which avoids trial for more explanation. – Raito Feb 01 '18 at 15:51
1

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)\,$.

dxiv
  • 76,497