1

The logic of the Inductive proof seems circular, the whole proof seems to hinge on whether or not the Inductive Hypothesis is true. Sure you can show that p(k+1) is true if p(k) is true, you have your instance of p(k) being true, and if p(k+1) is true than you can then treat p(k+1) as your new p(k) so on and so forth ad infinitum.

The trouble I have with the proof method is your given an example where p(k) is true but that doesn't mean that p(k) is always going to be true, for example.

Consider some arbitrary equation that is equal to zero at some point. Just because it's equal to zero at a particular point or even multiple points, that doesn't mean that it will always be true.

Positing that because p(k+1) can be proven to be true given your acceptance of p(k), doesn't feel like a real proof to me.

It doesn't feel like a real proof the way proof by contra-positive or proof by contradiction feel like real proofs.

Andrew
  • 385

3 Answers3

1

The axiom schema induction states that if a claim is true of $0$, and if when it's true of $k$ it's also true of $k+1$, then it's true of all non-negative integers. (That non-negative integers work this way is essentially part of the definition of non-negative integers.) Once both antecedents are proved, we're done.

J.G.
  • 115,835
0

That is the difference between ''induction'' and ''complete induction'' being the first true from some $n \in \mathbb{N}$ and on, and the second for all $n \in \mathbb{N}$. Of course the statement could be false is there is no $n$ that verifies the inductive hypothesis even when the induction step held. There are examples of this.

astro
  • 649
0

You didn't mention the basis step in your post, which leads me to believe that you may not have seen an intuitive explanation for the conclusion of induction.

Let's suppose that you have done what you were supposed to do in the inductive step: you have proved that for every $k \ge 1$, $p(k)$ implies $p(k+1)$.

You're right that this doesn't let you conclude the truth of $p(k)$ for any individual value of $k$: it doesn't let you conclude that $p(7)$ is true, nor $p(143)$, nor $p(348570956780634087340895739)$. It doesn't even let you conclude that $p(1)$ is true.

That's why you must also prove the basis step: You must prove $p(1)$ is true.

Once you've proved both the inductive step and the basis step, you could then bolster your intuition like this.

The truth of $p(1)$, and the truth of "$p(k)$ implies $p(k+1)$" for all $k \ge 1$, including for $k=1$ itself, immediately let's you conclude that $p(2)$ is true. No intuition yet, that's rock solid rigorous.

Next: the truth of $p(2)$, and the truth of "$p(k)$ implies $p(k+1)$" for all $k \ge 1$, including for $k=2$, immediately let's you conclude that $p(3)$ is true. No intuition yet, that's rock solid rigorous.

Next: the truth of $p(3)$, and the truth of "$p(k) \implies p(k+1)$" for all $k \ge 1$, including for $k=3$, immediately let's you conclude that $p(4)$ is true. No intuition yet, that's rock solid rigorous.

Next: the truth of $p(4)$ ...

Once you get tired of that, here's the intuition: what induction let's you do is to say "et cetera". Or if you prefer english to latin you can say "and so on". That is, induction let's you conclude what you would be able to conclude if you could continue on with "Next" infinitely many times, namely that $p(k)$ is true for all $k \ge 1$.

Lee Mosher
  • 120,280