1

In Induction, we do the following: Check $P(1)$ is true, then show that if $P(k)$ is true, then $P(k+1)$ is also true. So we proceed to assuming $P(k)$ is true, then attempt to show $P(k+1)$ is true, as the inductive hypothesize.

But are we allowed to say, assume $P(k-1)$ is true (this is my inductive hypothesize) and then show that $P(k)$ is true? If so, what is the (if any) advantage of doing this?

The same goes for Strong Induction.

frabala
  • 3,732
Lemon
  • 12,664
  • The advantage is that we are able to prove theorems for ALL natural numbers. It's like domino: if we know, the first domino will fall, then the second will. If the second falls, then the third will and so on. Now we have to make sure the first one falls and we know, they all fall. – Bernd Jan 10 '14 at 06:54
  • 1
    If $P(k) \implies P(k+1)$, let $i:=k+1$; you get $P(i-1) \implies P(i)$ – dani_s Jan 10 '14 at 07:01

2 Answers2

2

I assume here that you are doing induction on positive integers. There is no difference between the two approaches. In the first one, you formally prove $$\forall k\geq 1, P(k) \Rightarrow P(k+1)$$

whereas in the second one it is $$\forall k\geq 2, P(k-1) \Rightarrow P(k)$$

Proving $P(1)$ and any one of the two statements above will prove $\forall k\geq 1, P(k)$ by induction. The same goes for the so-called strong induction!

zarathustra
  • 4,891
  • I am reading this proof http://www.math.caltech.edu/~2011-12/1term/ma001a/11Ma1aNotesWk9.pdf and it fixes $m > 0$ and performances induction on $m$ but assuming $m-1$ is true. So doesn't this violate the fact that $m > 0$? – Lemon Jan 10 '14 at 07:04
  • @sidht They want to prove for all $m\in\mathbb N_0$, nt for $m\in \mathbb N$. Technically there is little difference aparet from the base case being $P(0)$ isntead of $P(1)$ and that you have to show $P(k)\Rightarrow P(k+1)$ for all $k\ge0$ instead of for all $k\ge 1$. - So they solve the base case $m=0$ (by saying that it's "trivial") and then for $m>0$ (that is: $m\ge 1$) show that $P(m-1)\to P(m)$. If things look confusing, always make sure that the first claimed use of the induction step starts with the base case on the left. Here: $m>0$ so $m-1\ge0$, starting with $P(0)\to P(1)$ is fine. – Hagen von Eitzen Jan 10 '14 at 07:16
  • In these notes, the induction is done on $\mathbb N$ (note the $m\geq 0$ in the statement of the lemma). The base case is $m=0$. The hereditary check is $$\forall m\geq 0, P(m) \Rightarrow P(m+1)$$ According to what I said in my answer, this is equivalent to $$\forall m\geq 1, P(m-1) \Rightarrow P(m)$$ but $m\geq 1$ is equivalent to $m>0$ when dealing with integers. Since we do induction for $m\geq 0$, and we take $m_0>0$, we still have $m_0-1 \geq 0$. Is it better? – zarathustra Jan 10 '14 at 07:16
  • They aren't any advantages, it is a matter of preferences! They use the "weak" induction, as the hypothesis is on all polynomials of degree exactly $m-1$, not on polynomials of degree at most $m-1$. – zarathustra Jan 10 '14 at 07:26
  • No, it doesn't. – zarathustra Jan 10 '14 at 09:13
  • How would the proof change if we wan to do $P(m) \implies P(m+1)$? Do we define $g(x) = xf(x) + C$? – Lemon Jan 10 '14 at 23:02
0

Yes, there is an advantage to using $P(k - 1) \Rightarrow P(k)$, it comes from structural induction.

You are probably familiar with performing induction on integers, proving $P(k+1)$ under the assumption $P(k)$. However, sometimes we wish to prove statements about countable objects like lists, graphs, multisets, matrices, etc, not just integers.

There are 2 forms you could take.
Form 1
Prove proposition $P(X)$, assuming it is true for all $P(Y)$ where $Y$ is a smaller version of $X$. For example, $X$ could be a list, and $Y$ could range over all lists that are 1 element smaller than $X$.

Form 2
Assuming proposition $P(Y)$, prove that $P(X)$ is true for all $X$ that are 1 step larger than $Y$. For example, you could assume $P(Y)$ holds for some graph $Y$, and attempt to prove that $P(X)$ holds for all graphs $X$ that have 1 more node than graph $Y$.

Clearly form 1 is easier to work with. Form 1 attempts to prove 1 statement from a large number of assumptions, whereas form 2 requires proving a large number of statements from 1 assumption.

Furthermore, in form 1 you get 1 more assumption to work with (sometimes you need it), you can assume that the statement you wish to prove is not the base case. So for integers:

Form 1
$$(k > 0) \land P(k - 1) \rightarrow P(k)$$

Form 2
$$P(k) \rightarrow P(k + 1)$$

Ok, not a big deal for integers because you only have a single "1 step larger" integer than $k$. However you get $k > 0$ for free, whereas $k + 1 > 0$, while easy to state, is obnoxious to have to state when needed. Also Form 1 prepares you better for induction on more interesting objects.

DanielV
  • 23,556