# Proof by induction - need help understanding this step...

• Apr 15th 2014, 01:40 PM
Bude8
Proof by induction - need help understanding this step...
http://puu.sh/8aaCd.png

Is the question. I've got the mark scheme, but I don't understand it ._.

http://puu.sh/8aaEx.png

How does
$(k+1)!-1+(k+1)(k+1)!$
become
$(k+1)![1+k+1]-1$

Logically, (k+1)(k+1)! should become the [1+k+1]
I'm probably just being retarded...
• Apr 15th 2014, 02:19 PM
Plato
Re: Proof by induction - need help understanding this step...
$\\(k+1)!-1+(k+1)(k+1)!=\\(k+1)![1+k+1]-1=\\(k+2)(k+1)!-1=\\(k+2)!-1$
• Apr 15th 2014, 02:28 PM
JeffM
Re: Proof by induction - need help understanding this step...
Quote:

Originally Posted by Bude8
http://puu.sh/8aaCd.png

Is the question. I've got the mark scheme, but I don't understand it ._.

http://puu.sh/8aaEx.png

How does
$(k+1)!-1+(k+1)(k+1)!$
become
$(k+1)![1+k+1]-1$

Logically, (k+1)(k+1)! should become the [1+k+1]
I'm probably just being retarded...

Students generally have a lot of trouble with proofs by induction. It does not seem to click intuitively at first.

One reason is the idiotic way it is presented: the notation used seems to imply that even though n = k also n = k + 1, which is pure nonsense.

Here is the intuitive idea. Suppose a proposition is true for 1. Suppose as well that if the proposition is true for k, it is also true for k + 1. So it is true for 1, but then it's true for 2, which means it is true for 3, and consequently it is also true for 4, and so on forever and ever and ever, world without end.

I like to think about the proof this way.

P(n) is a proposition about the positive integer n.

Step 1: Prove P(1).

As a result of step 1, we know that there is at least 1 and maybe more positive integers for which P is true. Choose an arbitrary one of them (call it k).

So it is not really an assumption that $k\ is\ a\ positive\ integer\ such\ that\ P(k)\ is\ true.$

We have chosen one of the positive integers for which P(k) is true, and we KNOW that at least one such positive integer exists.

Step 2: Prove P(k + 1) is true.

OK Let's look at your problem. The proposition is

$\displaystyle n \in \mathbb Z^+\ \implies \left(\sum_{i=1}^ni * i!\right) = (n + 1)! - 1.$

Step 1 is easy.

$\displaystyle n = 1 \implies \left(\sum_{i=1}^ni * i!\right) = 1 * 1! = 1 * 1 = 1 = 2 - 1 = 2 * 1 - 1 = 2! - 1 = (1 + 1)! - 1 = (n + 1)! - 1.$

Step 2

$Let\ k\ be\ an\ arbitrary\ positive\ integer \ such\ that\ \displaystyle \left(\sum_{i=1}^ki * i!\right) = (k + 1)! - 1.$

A very frequent approach to take is to break down an expression in (k + 1) into two expressions, one in k and the other in k + 1.

$\displaystyle \left(\sum_{i=1}^{k + 1}i * i!\right) = \left(\sum_{i=1}^ki * i!\right) + (k + 1) * (k + 1)! =$

$\{(k + 1)! - 1\} + (k + 1) * (k + 1)! =$

$\{(k + 1)! - 1\} + k * (k + 1)! + 1 * (k + 1)!=$

$(k + 1)! - 1 + k(k -1)! + (k + 1)!=$

$k(k + 1)! + 2(k + 1)! - 1 =$

$(k + 2)(k + 1)! - 1 =$

$(k + 2)! - 1 =$

$\{(k + 1) + 1)\}! - 1.$
• Apr 15th 2014, 03:44 PM
Plato
Re: Proof by induction - need help understanding this step...
Quote:

Originally Posted by JeffM
Students generally have a lot of trouble with proofs by induction. It does not seem to click intuitively at first. One reason is the idiotic way it is presented: the notation used seems to imply that even though n = k also n = k + 1, which is pure nonsense.

It will come as no surprise to you that a mathematician will totally disagree with that.
I completely understand how it appears idotic to anyone who does not understand what it means to say that the positive integers are well ordered. After all, the induction principle follows from the well ordering axiom.

Now how is it just for you to make that claim? That may well be the way induction is taught by the mathematics education community, who are by in large not mathematicians. (And it appears explainers such as you define yourself are not either.)

The logic is impeccable. If each non-empty subset of the positive integers has a first term and the set of the positive integers for which a statement is not true, then there is a first term, $J$, in that subset. If $P(1)$ is true then $J>1$. So $P(J-1)$ must be true.
But if $P(K)$ being true implies that $P(K+1)$ is true means that $P(J)$ must be true. That is a contradiction. Thus that set for which $P(n)$ is false is empty.
• Apr 15th 2014, 06:05 PM
JeffM
Re: Proof by induction - need help understanding this step...
Quote:

Originally Posted by Plato
It will come as no surprise to you that a mathematician will totally disagree with that.
I completely understand how it appears idotic to anyone who does not understand what it means to say that the positive integers are well ordered. After all, the induction principle follows from the well ordering axiom.

Now how is it just for you to make that claim? That may well be the way induction is taught by the mathematics education community, who are by in large not mathematicians. (And it appears explainers such as you define yourself are not either.)

The logic is impeccable. If each non-empty subset of the positive integers has a first term and the set of the positive integers for which a statement is not true, then there is a first term, $J$, in that subset. If $P(1)$ is true then $J>1$. So $P(J-1)$ must be true.
But if $P(K)$ being true implies that $P(K+1)$ is true means that $P(J)$ must be true. That is a contradiction. Thus that set for which $P(n)$ is false is empty.

I am not sure what we are disagreeing about. I certainly do not claim to be a mathematician, and I never have been a professional teacher, but I do have some experience trying to teach young people math: in general, they initially find proofs by induction very unintuitive. I blame the way such proofs are introduced to students. Perhaps I am wrong, but you do not say why I am wrong. You seem to think that I am challenging proof by inductions. If I created that impression, I apologize because it was not my intent.

I see time and time again confusion about what n is supposed to mean in proofs by induction. And why say "assume" there exists k? With step 1 it has been demonstrated that the set of positive integers for which the proposition is true is not empty. No assumption whatsoever is required about the existence of k. And if someone says n = k, then that someone should not also say n is any positive integer or n = k + 1. If n is supposed to represent any positive integer, then k is legitimate only as an arbitrary element of the set of positive integers for which the proposition is true. Step 1 of course has already proved that the relevant set is not empty. Step 2 then shows that the proposition is true of successors.

$P(1)\ is\ true\ and\ P(k + 1)\ is\ true\ for\ every\ positive\ integer\ for\ which\ P(k)\ is\ true \implies$

$P(n)\ is\ true\ for\ any\ n\ that\ is\ a\ positive\ integer$ is an argument that can be made intuitively persuasive and the logic of such proofs is then readily comprehensible.

What is it we are disagreeing about anyway?
• Apr 16th 2014, 12:34 AM
Bude8
Re: Proof by induction - need help understanding this step...
Quote:

Originally Posted by Plato
x

Quote:

Originally Posted by JeffM

$\{(k + 1)! - 1\} + (k + 1) * (k + 1)! =$

$\{(k + 1)! - 1\} + k * (k + 1)! + 1 * (k + 1)!=$

$(k + 1)! - 1 + k(k -1)! + (k + 1)!=$

$k(k + 1)! + 2(k + 1)! - 1 =$

$(k + 2)(k + 1)! - 1 =$

$(k + 2)! - 1 =$

$\{(k + 1) + 1)\}! - 1.$

Sorry guys, I'm probably being incredibly thick but I still don't get it.

I get where the (k+2)! comes from - multiplying (k+1)! by (k+2), which is the [1+k+1] bit. But I don't get that bit. How do you go from
(k+1)(k+1)! to [1+k+1]?

T_T
• Apr 16th 2014, 03:09 AM
Plato
Re: Proof by induction - need help understanding this step...
Quote:

Originally Posted by Bude8
Sorry guys, I'm probably being incredibly thick but I still don't get it.

I get where the (k+2)! comes from - multiplying (k+1)! by (k+2), which is the [1+k+1] bit. But I don't get that bit. How do you go from
(k+1)(k+1)! to [1+k+1]?

Factor out a common factor, $\color{red}{(k+1)!}$

$\\\color{red}{(k+1)!}-1+(k+1)\color{red}{(k+1)!}=\\\color{red}{(k+1)!}[1+k+1]-1=\\(k+2)\color{red}{(k+1)!}-1=\\(k+2)!-1$