I'm going to put out two strong induction questions that seem different in the base cases.

Question 1: Prove that $u_n = 4^n + 6^n$ if $u_0 = 2, u_1 = 6$ and $u_{n+2} = 6u_{n+1} - 8u_{n}$.

I know that we would have to show the base cases $P(0)$ and $P(1)$ are true (which are true by definition of the sequence $u_n$).
This means we had to take two base cases here, since we want to show that $P(k-1), P(k)$ being true implies $P(k+1)$ is true.

Question 2: Every integer greater than $1$ is the product of primes.
For this question they only took one base case, that is, by showing $P(2)$ is true and then assumed true for $P(n)$ for all integers $2\leq n \leq k$. I would have thought that since we want to prove $P(k),P(k-1),\ldots,P(2)$ implies $P(k+1)$ is true, we would need to have $k-1$ amount of base cases... which doesn't make sense anyway....

Why does the first question require taking two base cases whereas the second question only took one base case, even when it's dealing with more than $2$ assumptions (since $k\geq 2$)?

Here is the proof I am looking at for question 2:

Also, looking at another example: http://www.mathblog.dk/strong-induction/,
the author took 6 base cases which makes sense as in question 1.

  • 1
    $\begingroup$ In Question 1, $u_{n+2}$ definition requires two values: $u_{n+1}$ and $u_{n}$. If you know $u_0$ only, how do you compute $u_1$ from the recurrence relationship? $\endgroup$ – Math Lover Aug 24 '17 at 1:39
  • $\begingroup$ Did you mean $u_n = -4^n+6^n$ or perhaps $u_{n+2}=6u_{n+1}+8u_n$? Because what you want to prove doesn't currently hold: $4^2+6^2=52\not =20=6(6)-8(2)$. $\endgroup$ – Vedvart1 Aug 24 '17 at 4:15

Actually, the proof for the first question doesn't really use strong induction, but uses what is sometimes called 'strong weak induction': you make reference to a fixed number of earlier cases (in this case, two) and you know exactly what those previous cases are (in this case, the two previous numbers). In fact, it is those latter cases that determine how many base cases there should be. For example, if your recursive relation was $u_{n+4} = 4u_{n+2} - 2u_n$, then it is clear you need $4$ base cases, for only after those first $4$ can you get the recursion up and running.

The proof for the second question does use a genuine case of strong induction, since you prove $P_{k+1}$ on the basis of all of the $P_1$ through $P_k$ (or, in this case, $P_2$ through $P_k$). So note that there is no longer a fixed number of cases to which we refer back (as it changes for each $k$), and it is also no longer clear which specific cases you use; you simply assume they all hold as the inductive hypothesis.

Now, depending on how you look at it, strong induction can in fact be said to have no 'base' cases at all: you simply show that the claim holds for any $k$ if you assume it holds for all previous ones: do this for any $k$, and you're done! No separate base cases needed. In practice, though, the very first one is a bit of an exception, in that it has no previous ones (in your case, there is no relevant case smaller than $2$, since the claim is about all whole numbers greater than $1$). So this means that you need to prove the case $P_2$ on the basis of nothing, i.e. you simply need to prove the case $P_2$ in and of itself .... which is why this first case is often seen as 'the base case' for strong induction.

| cite | improve this answer | |

While unrelated to the base case problem, I think what you want to prove for the first question is actually not true, but correct me if something I've done is wrong.

Assume $u_n=4^n+6^n$ for $1\le k\le N$. Then

$$ \begin{align} u_{N+1}&=6u_N-8u_{N-1}\\ &=6(4^N+6^N)-8(4^{N-1}+6^{N-1})\\ &=3*2^{2N+1}+6^{N+1}-2^{2N+1}-3^{N-1}*2^{N+2} \\ &=2*2^{2N+1}+6^{N+1}-8*6^{N-1}\\ &=4^{N+1}+6^{N+1}-8*6^{N-1} \\ &\not =4^{N+1}+6^{N+1} \end{align} $$

So surely you typed something wrong or I've erred somewhere, as this means that an attempt at strong induction actually disproves the statement you're trying to prove.

| cite | improve this answer | |

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.