Vrftsjtryk

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 :)

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

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+3implies b_n=2b_{n-1}+k+3$$ If you choose $k+3=0$, what do you find ?

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 - 3lambda + 2 = 0 iff \
(lambda - 1)(lambda -2) = 0
$$

Thus your recurrence will be in the form:
$$
a_{n} = C_1lambda_1^{n} + C_2lambda_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 + 3cdot2^n
$$