# Induction, not what, but how it's done?

I have a simple formula for the n-th derivative of some expression. I'm suppose to prove that it's true for all N, by using induction. I set n=1, and show that the base case works.

The next step, were I assume that it works a K is fine. But how is that shown on paper? And the that I don't understand at all, is how to show algebraically that this is true. Do you just "plug-in", replace all the k's with k+1 and then what? Or? Well as you see, I don't get it.

Thank you so much for any input :)

-
You can ask further questions if you can refine this one based on new understanding. – anon Nov 7 '10 at 13:33

The principle of induction says that if you have some $\mathbb N$ indexed family of propositions $P(n)$, that you can prove the theorem $\forall n \in \mathbb N, P(n)$ just by proving:

• $P(1)$
• $\forall n \in \mathbb N. P(n) \Rightarrow P(n+1)$

Intuitively this is quite simple, for any given number say 3051 the statement P(3051) must be true, since P(0) is true, P(1) is true, P(2) is true ... all the way up to P(3051). Mathematically this is just reflecting the nature of $\mathbb N$ so it's a tautology.

It is probably not clear what a proposition is though, because nobody ever talks about them. Well if you are familiar with functions, like $f(x) = x^2-1$, given any number say 3 you find that f(3) is a number too: 8. A proposition is like a function except that it computes a mathematical statement.

I could define the following proposition: $S(x) :\iff \exists n, n^2 = x$ and that would hold for all square numbers for example $S(9) \iff \exists n, n^2 = 9$ and so we can prove $S(9)$ by proving $\exists n, n^2 = 9$ by exhibiting the witness 3 then showing that $3^2 = 9$.

A much more interesting example might be the proposition $\text{Strong}_P(n)$ which is defined like so:

• $\text{Strong}_P(1) :\iff P(1)$

• $\text{Strong}_P(2) :\iff P(1) \text{ and } P(2)$

• $\text{Strong}_P(3) :\iff P(1) \text{ and } P(2) \text{ and } P(3)$

• ...

• $\text{Strong}_P(n+1) :\iff \text{Strong}_P(n+1) \text{ and } P(n+1)$

It is relatively easy to verify that $\text{Strong}_P(n) \iff (\forall k \leq n, P(k))$ so this really is the principle of "strong" induction. Furthermore you can prove the definition holds for all $n$ using normal induction.

A very beautiful theorem is that the sum of cubes is the square of the sum, e.g.

$$1^3 + 2^3 + 3^3 + 4^3 + 5^3 = (1 + 2 + 3 + 4 + 5)^2$$

So let $P(n)$ be the statement "sum of cubes up to n = square of sum up to n". Obviously it holds for P(1) since 1 = 1, now we would like to prove $\forall n \in \mathbb N. P(n) \Rightarrow P(n+1)$:

for all n, given that the sum of cubes up to n equals the square of the sum of to n, then "the same statement for n+1".

So we have the assumption $1^3 + 2^3 + \cdots + n^3 = (1 + 2 + \cdots + n)^2$ and need to prove $1^3 + 2^3 + \cdots + n^3 + (n+1)^3 = (1 + 2 + \cdots + n + n+1)^2$.

Now we use algebra, the right hand side is $(1 + 2 + \cdots + n)^2 + 2(n+1)(1 + 2 + \cdots + n) + (n+1)^2$. So all we have to show now is that $(n+1)^3 = 2(n+1)(1 + 2 + \cdots + n) + (n+1)^2$.

Multiplying out some things $n^3 + 3 n^2 + 3 n + 1 = 2(n+1)(1 + 2 + \cdots + n) + n^2 + 2 n + 1$ cancelling some things gives: $n (n + 1)^2 = 2(n+1)(1 + 2 + \cdots + n)$ and we quickly notice it being equivalent to the formula $(1 + 2 + \cdots + n) = n (n + 1)/2$.

Shall we try to prove this by induction also! Let $T(n)$ be the statement that $(1 + 2 + \cdots + n) = n (n + 1)/2$. Clearly T(1) holds, since 1 = 1. Now we should like to prove that for any given $n$ the hypothesis $T(n)$, that is $(1 + 2 + \cdots + n) = n (n + 1)/2$ implies that $(1 + 2 + \cdots + n + n+1) = (n + 1) (n + 2)/2$. Algebraically we can just substitute the hypothesis in to get $n (n + 1)/2 + n+1 = (n + 1) (n + 2)/2$ doubling this $n (n + 1) + 2 n + 2 = (n + 1) (n + 2)$ and this is obviously true by multiplying out both sides.

(this was a stupid example though beacuse you can just check the first 4 cases and not do any induction).

-
Thank you for trying, but I didn't really get that :( – Algific Nov 7 '10 at 13:03
You've spent less than 10 mins reading this and you already give up? That's ridiculous. – anon Nov 7 '10 at 13:03
@Algific: muad gave a straightforward explanation; what part didn't you understand? You prove that an expression is valid for a base case, assume that what you're proving is valid for k, and then prove the validity for k+1. Nothing more to it! – J. M. Nov 7 '10 at 13:09
How do you do the k+1 part? Do I replace K with k+1? And set that new equation equal to the old one? – Algific Nov 7 '10 at 13:12
@Algific, I've added another (two) examples. – anon Nov 7 '10 at 13:20

Here is a very simple illustrative example.

Lemma $\rm\quad D^ne^{cx}\ =\ c^n e^{cx }\quad$ for all $\rm\:n\in \mathbb N$

Base step: $\$ It is true for $\rm\, n = 0\,$ since $\rm\, D^0 = I, \ \ c^0 = 1.$

Induction step: $\$ If it is true for $\rm\, n\,$ then differentiating both sides yields

$\rm\qquad\qquad\ \ D^{n+1} e^{cx}\ =\ D (c^n e^{cx })\ =\ c^{n+1} e^{cx}$

hence it is true for $\rm\, n+1.\,$ Therefore it is true for all $\rm\,n\in \mathbb N\,$ by induction.

-

muad's answer is clear, but one could emphasize a couple of points:

Mathematical induction is essentially a logical chain reaction. It helps to visualize the goal $\forall n\ P(n)$'' as an infinite number of separate assertions $P(1), P(2), \ldots$ The aim of the induction step is to establish logical links between successive assertions: $$P(1)\Rightarrow P(2)\Rightarrow \ldots \Rightarrow P(17)\Rightarrow P(18)\Rightarrow\ldots$$ That is, $\forall n\in\mathbb N\ P(n)\Rightarrow P(n+1)$. These links are purely hypothetical inferences.

The handout here provides an expanded explanation with examples.

-
"A => B => C" is very bad form. What you really mean is probably "A => B and B => C". This is (or at least should be) always hammered into the heads of 1st year students who are used to using implication arrows rather willy-nilly from high school. – kahen Nov 7 '10 at 16:44
I believe students find the image of a chain a compelling visualization of the nature of inference via induction. As I indicated, in teaching one also carefully emphasizes that each link has a hypothesis and a conclusion and how one gets from one to the other. If one wants students to develop skill in explaining their reasoning, insist (as I do) that they write certain solutions in complete grammatical sentences. – Bob Pego Nov 13 '10 at 4:08

So you get it conceptually (assume $P$ true for an arbitrary $n$, show that that implies $P$ true for $n+1$) (and yes that seems weird but if you parenthesize the formula with quantifiers, it works out that you're not really assuming the consequent).

But in practice...that's what you want to know how to do it. Examples are best. Let's try a simple one that you've probably seen before but specify exactly what is happening. For

$\sum_{k=0}^{n-1} 2k+1 = n^2$

in the inductive case, assume the above is true, then show that the LHS with $n+1$ substituted for $n$ equals the RHS with the same substitution. That is, show

$\sum_{k=0}^{n} 2k+1 = (n+1)^2.$

The strategy is to do algebraic manipulation so that you see where you can apply the induction hypothesis. You can do the manipulation on either side, but you have to follow the rules (here specifically when proving an equational identity, i.e. 'LHS = RHS', you have to make sure you keep them separate, that is show a chain of manipulation leading from one to the other.

You can start from either side: the RHS obviously expands to $n^2 + 2n + 1$. Now use your pattern matching skills to find something that looks like something in the induction hypothesis. Here it would be the $n^2$ part. This looks like the RHS of the induction hypothesis; you can replace it with the LHS (of the induction hypothesis), to get

$(\sum_{k=0}^{n-1} 2k+1) + 2n + 1$

(extra parens put in to show what got replaced) And the extra part outside of the summation, the $2n+1$, is the same as extending the top of the range of the summation to $n$ (here you have to be familiar with the summation notation). So this last part can be converted immediately into

$\sum_{k=0}^{n} 2k+1$

But that is the end of the equational chain, going from $(n+1)^2$ to $\sum_{k=0}^{n} 2k+1$, maintaining equality the the whole way, most of the time just doing the algebraic manipulation, but necessarily using the induction hypothesis somewhere along the line, that is,

$(n+1)^2 = ... = ... = \sum_{k=0}^{n} 2k+1$

I'd suspect a lot of the difficulty here is just keeping separate what you know already and what you have to prove (what you don't actually know yet -in- the proof). And ...yeah...just keeping track of all the symbols.

-