2
$\begingroup$

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

....

$\endgroup$
5
  • 1
    $\begingroup$ What have you tried? $\endgroup$
    – David P
    Commented Oct 12, 2020 at 2:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – KingLogic
    Commented Oct 12, 2020 at 2:45
  • $\begingroup$ Apologies. I have edited my question with the work I have so far @KingLogic $\endgroup$
    – maria
    Commented Oct 12, 2020 at 3:12
  • $\begingroup$ @DavidP See the above $\endgroup$
    – maria
    Commented Oct 12, 2020 at 3:12
  • $\begingroup$ 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. $\endgroup$
    – Darsen
    Commented Oct 28, 2020 at 17:19

1 Answer 1

1
$\begingroup$

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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .