# Using strong induction vs strong induction with a recurrence. How both differ

How would I go about solving a strong induction problem with a recurrence? Does it still follow setting up a base case, inductive hypothesis and inductive step? For ex. how would I go about solving the following problem?

Use strong induction to prove that $$C(n)=2^n+3$$ is a solution to the recurrence $$C(0)=4$$, $$C(1)=5$$, and $$C(n)=3\cdot C(n-1)-2\cdot C(n-2)$$ for all $$n\in\mathbb{Z+}$$, $$n>1$$.

Thank you very much for the help.

My work so far:

Base case:

For n=2

$$C(2) = 3C(2-1)-2C(2-2)$$

$$C(2) = 3C(1) - 2C(0)$$ Using the given C(0) =4 and C(1) =5

$$C(2) = 7$$

$$C(2) = 2^2 + 3 = 7$$

For the induction hypothesis:

Assume $$C(n) 2^n +3$$

$$n = 0, 1 ... k$$

Induction Step:

Prove for n = k+1

$$C(k+1) = 3C(k+1-1) -2C(k+1-2)$$

....

• What have you tried? Commented Oct 12, 2020 at 2:40
• Welcome to Math SE! In this community of mathematicians and math enthusiasts, it is recommended that you add what you have tried so far, so we can help you better. Commented Oct 12, 2020 at 2:45
• Apologies. I have edited my question with the work I have so far @KingLogic Commented Oct 12, 2020 at 3:12
• @DavidP See the above Commented Oct 12, 2020 at 3:12
• If one of the answers below answered your question, the way this site works works, you'd "accept" the answer, more here: What should I do when someone answers my question?. But only if your question really has been answered. If not, consider adding more details to the question. Commented Oct 28, 2020 at 17:19

The base cases $$C(0)$$ and $$C(1)$$ are easy to check. Now, strong induction says that you have to suppose the statement is true for every number from the first case up to some $$n$$ (included), and then be able to prove that it holds for $$n+1$$ too. It just takes into account every case we have checked before making the induction step to the next case.
Suppose the statement is true for every number from $$0$$ up to some $$n\ge 1$$ (we can say this last part because we checked the statement holds for $$1$$ too). Consider $$C(n+1)=3C(n)-2C(n-1)$$. Since $$n,n-1\le n$$, the statement holds for them, so $$C(n)=2^n+3$$ and $$C(n-1)=2^{n-1}+3$$ (here we needed that $$n\ge 1$$ to get $$n-1\ge 0$$, since there is no case for negative numbers).
So $$C(n+1)=3(2^n+3)-2(2^{n-1}+3)=3·2^n-2^n+9-6=2·2^n+3=2^{n+1}+3$$.