# Recurrence Substitution Method with multiple givens

Solve by using the substitution method $T(n)=T(n-1)+2T(n-2)+3$
Given $T(0)=3$ and $T(1)=5$

I kind of understand it with only one given and one recurrence call by expanding the call using what is inside.
ex. if it was $T(n)=T(n-1)+3$
Given $T(1)=5$
I would take the $n-1$ and plug it into the the first equation $T(n)=T(n-1)+3$
and repeat until I can find a general case. After that simplify it to get my answer.

My problem is when I have two givens and two recurrences. I first though about solving each one separately using the first recurrence and then the second but it wasn't making any sense to me.

• This is really a math question. Aug 5 '18 at 23:24

## 1 Answer

Let $S(n) = T(n) + 1.5$. Then $$S(n) = T(n) + 1.5 = T(n-1) + 2T(n-2) + 4.5 = S(n-1) + 2S(n-2).$$ The recurrence $S(n) = S(n-1) + 2S(n-2)$ is homogeneous with constant coefficients, so we know how to solve it. We first solve the equation $\lambda^2 = \lambda + 2$, finding that the solutions are $2,-1$. This implies that there exist constants $A,B$ such that $$S(n) = A 2^n + B (-1)^n.$$ Since $S(0) = 4.5$ and $S(1) = 6.5$, we see that $A + B = 4.5$ and $2A - B = 6.5$, from which we find that $A = 11/3$ and $B = 5/6$. Therefore $$T(n) = \frac{11}{3} 2^n + \frac{5}{6} (-1)^n - \frac{3}{2}.$$

• Ah, so two questions then. The first is how did you get the $+1.5$ at then end? The other would be with the new formula do I just just check that the two givens are correct? Aug 6 '18 at 1:41
• I guessed that $S(n) = T(n) + C$ would result in a homogeneous recurrence, and solved for $C$. To verify that I got the correct formula for $T(n)$, you can use proof by induction. Aug 6 '18 at 1:44