1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is really a math question. $\endgroup$ – Yuval Filmus Aug 5 '18 at 23:24
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – zSkeeter135 Aug 6 '18 at 1:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Aug 6 '18 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.