Trouble solving recursive function

Question

I have trouble solving a (what looks like very easy) recursive function

$a_0 = 0 \\ a_n = 2a_{n-1}+3$

Hints/Techniques for how to solve this would be highly appreciated!

Thanks :)

Answer 1

• Write out the first few terms.
• Notice that they're divisible by $3$.
• Divide them by $3$.
• Recognise the resulting sequence.
• Prove your formula by induction.

Answer 2

One of the ways could be as follows. Write down the formula for $n$-th and $n+1$-th terms. We want to translate the non-homogenous recurrence relation into a homogenous one. This means we want to get rid of the $3$ from the recurrence. $$ a_n = 2a_{n-1} + 3\\ a_{n+1} = 2a_{n} + 3 $$

Subtract both equalities: $$ a_n - a_{n+1} = 2a_{n-1} + 3 - (2a_{n} + 3) \\ -a_{n+1} = 2a_{n-1} - 2a_n - a_n \\ a_{n+1} = 3a_n - 2a_{n-1} \\ a_{n+1} - 3a_n + 2a_{n-1} = 0 $$

Now writing down a characteristic equation for this you may obtain: $$ \lambda^2 - 3\lambda + 2 = 0 \iff \\ (\lambda - 1)(\lambda -2) = 0 $$

Thus your recurrence will be in the form: $$ a_{n} = C_1\lambda_1^{n} + C_2\lambda_2^{n} $$

Using initial conditions lets find the coefficients. We're given: $$ \begin{cases} a_0 = 0 \\ a_1 = 3 \end{cases} $$

Now solve a simple linear system: $$ \begin{cases} C_1(1)^{0} + C_2(2)^{0} = 0\\ C_1(1)^{1} + C_2(2)^{1} = 3\\ \end{cases} \\ \begin{cases} C_1 + C_2 = 0\\ C_1 + 2C_2 = 3\\ \end{cases} \\ \begin{cases} C_1 = -3\\ C_2 = 3 \end{cases} $$

Thus your recurrence is given by: $$ a_{n} = -3 + 3\cdot2^n $$

Answer 3

Hint

A small trick for such kind of recurrence relation $$a_n=2a_{n-1}+3$$ Let $a_n=b_n+k$ and replace $$b_n+k=2b_{n-1}+2k+3\implies b_n=2b_{n-1}+k+3$$ If you choose $k+3=0$, what do you find ?