I'm trying to understand proof by induction rigorously. Is it based on assumptions?

Question

My understanding of the reason for using proof by induction is to see if the expression used to calculate what the nth term in a sequence is, always holds or not.

A proof by induction requires a basis step. It's not explicitly stated why the basis step is important when learning this. I hear analogies that proof by induction is like a ladder, like dominoes, like stairs, so I think to myself what is similar about those objects. The segments of a ladder, or stairs all look identical to each other going all the way up the ladder or all the way up the stairs.

This leads me to believe there is an assumption that an equation performs an identical action on each of the numbers inputted into it. Which seems reasonable to me. An equation performs the same action on the number 2, whether it be scaling it, adding to it, etc, that it would perform on the next number, say 3.

Some expressions are hard to see exactly what the pattern would be, but by looking at the a few terms in the pattern we notice certain pattern, sometimes that pattern does break and we discover the actually equation that would hold that pattern forever is different from what we thought it was originally.

So this is where the distinction that we assume the expression we are given originally is correct, in the induction hypothesis we use the logical expression know as implication, "If p then q" if you recall the truth table for that expression it can only be proven to be false when p is true and q is false. So the truth of p is actually irrelevant, we are checking to see that if p were true than would q hold.

We test the induction hypothesis by setting the original equation on one side of an equals symbol, adding the k+1 last term to it, then we put the expression with the k+1 replacing every instance of k. We massage the equations to see if they look identical, and if they do we can see our equality holds.

I'm not really sure why we bother doing all of this in the first place, If we are assuming our propositional statement is true to begin with, and if we know from the onset that our equation behaves like a ladder or stairs, can't we just infer from the very beginning that k+1 holds . .

I'm not too certain what the point of the proof really is. It still seems circular to me. I must be missing some really important insight. I don't want to just route memorize this. I get some of the basic ideas of the proof and I think I understand what it's trying to accomplish, it just doesn't seem rigorous like proof by contradiction or proof by contra positive.

Answer 1

Try thinking about the domino metaphor. We have infinitely many dominoes and we want to prove that they all fall down. When we prove the base-step we have proven that the first domino falls. When we prove the induction step we prove that when the nth domino falls, the (n+1)th domino falls as well. As the first one falls, the second must also fall down and as the second falls down, the third falls down and so on and therefore all of the dominoes fall.

Answer 2

You have implied in your post that you are happy with proof by contradiction.

You can think of any proof by induction as a form of proof by contradiction.

For example, suppose you are trying to prove that $\sum_{i=1}^n i=\frac{1}{2}n(n+1)$ for all positive integers $n$.

A proof by contradiction might go like this:-

Suppose the result is false.

Then there is some positive integer $n$ for which $\sum_{i=1}^n i\ne\frac{1}{2}n(n+1)$. Since $1=\frac{1}{2}\times 1\times2$, the result is true for $n=1$ so suppose the smallest $n$ for which the result is false is $n=k+1$.

The result is true for $n=k$ and therefore $\sum_{i=1}^k i=\frac{1}{2}k(k+1)$. Then $$\sum_{i=1}^{k+1} i=\frac{1}{2}k(k+1)+(k+1)=\frac{1}{2}(k+1)(k+2).$$

The result is true for $n=k+1$ after all, a contradiction. We conclude there are no counterexamples.

In the above you should be able to spot the analogue of the base case and the inductive step. So, if you're happy with proof by contradiction, you can also be happy with induction.

Answer 3

induction follows:

Base case

This is used to establish that there is a case where it's true.

Induction step

This is used to show if there is a general case that's true ( see for example the base case), it leads to another case that's true (the next case we are considering hopefully).

The reason we need both parts, is because either the induction step can fail, or if it suceeds, there need not be a base case where it's true.

for example, lets hypothesize that if $2^n-1$ is prime $2^{n+2}-1$ is prime, well $2^n-1$ is prime for $n=2$ (it's equal to 3, base case established) but $2^{n+2}-1=4(2^{n}-1)+3$ which when the parenthesized expression is 3 or a multiple of it, makes the whole expression have a factor of 3 ( clearly composite unless 3 is of form $4k+1$), this means our induction step would fail as it's not generally true.