Using substitution in an inductive proof

[dane502]

I am to prove something inductively. Can one substitute as follows?

For the inductive part, assume that
(*) n_k < n_(k+1)

In order to show that this implies:
(**) n_(k+1) < n_(k+2),

Can one then simply make the substitution k+1 = s in (**), yielding
n_(s) < n_(s+1)?

 

[CompuChip]

The answer is yes, if the assumption is that it holds for all k.

Usually though, in an inductive prove you assume that (*) only holds for all k up to some fixed value (say, K) and you want to prove that it also holds for k = K + 1.

 

[dane502]

Okay, so if my proof consisted of proving, that
n_1 < n_2

and then using the "induction" used in my previous post, it wouldn't complete the proof that

n_k < n_(k+1) for all integers, k?

 

[CompuChip]

No, unfortunately not.

As a very simple example, consider n_k = k⁴ - 2 k².
It is very easy to show that 0 = n_0 &gt; n_1 = -1, but n_k &lt; n_{k + 1} for all other k (so if you take 2k² - k⁴ to flip the < and > signs in my example and shift the whole sequence by 1 you will get precisely what you asked, starting at k = 1).

The idea of induction is, that if you know that a statement holds for all integers up to some value, you can prove it for the next one. And then if it holds up to k = 1, you have shown that it holds for k = 2, from which it follows for k = 3, hence for k= 4 ,etc.

 

[CompuChip]

Here is a post that I wrote earlier, that tries to explain proof by induction in more detail. Hopefully it helps.

Generally, when you have some statement like "for all n, X is true", a proof by induction consists of two steps. First, you have to show that for some simple case (usually n = 0 or 1, depending on the question), X is true. Then you assume that X is true for all integers n up to some given value n₀, and you prove that under that assumption, X is also true for n₀ + 1.

The reasoning is then as follows: you have checked by hand that it is true for n = 1. You have proven that if it is true for n₀ = 1 (which it is), then it is true for n = n₀ + 1 = 2. So it is true for n = 2. Also, you have shown that if it is true for n = 2, it is true for n = 3. Since it is true for n = 2, it holds for n = 3. Similarly, it is true for n = 4, and for n = 5, and so on.

Note that proof by induction is a convenient way (once you are used to it) to prove such statements "for all n", but it doesn't help you to find the statement. So if instead of "prove that the nth derivative is ...formula..." you get "derive and prove a formula for the nth derivative", you will first need to come up with a hypothesis by some other way. Once you have the hypothesis, you can make it into a theorem and try to prove it by induction.