Example: 'The sum of the natural numbers from 1 to n equals n(n+1)/2'.
This is a property which depends on n. We write this fact as E(n).
E(3) means in our example :
' The sum of the natural numbers from 1 to 3 equals 3(3+1)/2'.
A proof by induction is a common method to prove such a property. We show how the method works and why it is correct.
Let V = { n | E(n) is true }. First we prove E(1). Then we know that 1 is in V.
Then we prove that: If E(k) is true, then E(k+1) is true.
If that is proved, we know that: if k is in V then (k+1) is in V.
But 1 is in V, so 2 is in V, so 3 is in V, etc...
Then V = { 1,2,3,4,....}
We have shown that the property E(n) is true for all natural numbers starting with 1.
We'll show the truth of E(1). We have to show: 1 = (1+1).1/2
We see immediately that both sides are equal. So, E(1) is true.
V contains '1'.
Assume for a moment that E (k) is true.
Given : 1+2+3+4+5+...+k = (1+k)k/2
We'll show the truth of E(k+1).
Proof:
left side = (1+2+3+4+5+...+k)+ (k+1) = (1+k).k/2 + (k+1) = (k+1)(k+2)/2
right side = (1+(k+1)).(k+1)/2 = (2+k)(k+1)/2
Thus if E (k) is true then E(k+1) is true.
If k is in V, then k+1 is in V.
But 1 is in V, so 2 is in V, so 3 is in V, etc..
So, V = { 1,2,3,4,....}
We resume the same example, but give the short version.
We have to prove: 1+2+3+4+5+...+ n = (1+n)n/2
Proof:
If n=1 then the property is true because 1 = (1+1).1/2
Now assume that the property is true for n= k
We'll show the validity of the property for n= k+1.
We have to prove: 1+2+3+4+5+...+k+(k+1) = (1+(k+1)).(k+1)/2
Left side = (1+2+3+4+5+...+k)+ (k+1) = (1+k).k/2 + (k+1) = (k+1)(k+2)/2 = right side
So, the property is true for all natural numbers starting from 1.
Show that for all integers greater than zero : 2^{n} >= n+1. |
The property is obvious for n = 1.
Now assume that the property is valid for n=k
So, we know that 2^{k} >= k+1.
It is very important that we use this, in the remainder of our proof
We have to prove that property is valid for n = k+1
We have to prove: 2^{k+1} >= k+2
Well, 2^{k+1} = 2^{k}.2 >= (k+1).2 = 2k+2 >= k+2
So the property is valid for all n.
Prove by induction that S_{n} = 1 + 3 + 5 + 7 + ... + 2n-1 = n^{2} |
The property is obvious for n = 1.
Now assume that the property is valid for n=k
So, we know that S_{k} = 1 + 3 + 5 + 7 + ... + 2k-1 = k^{2}
It is very important that we use this, in the remainder of our proof
We have to prove that property is valid for n = k+1
We have to prove: S_{k+1} = 1 + 3 + 5 + 7 + ... + 2k-1 + 2k+1 = (k+1)^{2}
Well, S_{k+1} = S_{k} + (2k+1) = k^{2} + 2k +1 = (k+1)^{2}.
So, the property is true for all natural numbers starting from 1.
Prove by induction that 1^{2} + 2^{2} + 3^{2} + ... + n^{2} = (1/6). n.(n+1).(2n+1) |
The property is obvious for n = 1.
Now assume that the property is valid for n = k
So, we know that 1^{2} + 2^{2} + 3^{2} + ... + k^{2} = (1/6). k.(k+1).(2k+1)
It is very important that we use this, in the remainder of our proof
We have to prove that property is valid for n = k+1
We have to prove: 1^{2} + 2^{2} + 3^{2} + ... + k^{2} + (k+1)^{2} = (1/6).(k+1).(k+2)(2k+3)
Left side = 1^{2} + 2^{2} + 3^{2} + ... + k^{2} + (k+1)^{2} = (1^{2} + 2^{2} + 3^{2} + ... + k^{2}) + (k+1)(k+1) = (1/6). k.(k+1).(2k+1) + (k+1)(k+1) = (1/6).(k+1). [ k(2k+1) + 6(k+1)] = (1/6).(k+1).(2 k^{2} + 7k + 6) Right side = (1/6).(k+1).(k+2)(2k+3) = (1/6).(k+1).(2k^{2} + 3k + 4k + 6)
Show that 3^{2n+1} + 2^{n-1} is a multiple of 7 |
The property is obvious for n = 1.
Now assume that the property is valid for n = k
So, 3^{2k+1} + 2^{k-1} is a multiple of 7
It is very important that we use this, in the remainder of our proof
We have to prove that property is valid for n = k+1
We have to prove: 3^{2k+3} + 2^{k} is a multiple of 7
We transform 3^{2k+3} + 2^{k} such that 3^{2k+1} + 2^{k-1} shows up.
3^{2k+3} + 2^{k} = 3^{2}.3^{2k+1} + 2.2^{k-1} = 9. 3^{2k+1} + 2. 2^{k-1} = 7. 3^{2k+1} + 2. 3^{2k+1} + 2. 2^{k-1} = (multiple of 7) + 2 (3^{2k+1} + 2^{k-1}) = (multiple of 7)+ 2 . (multiple of 7) = (multiple of 7)
Show that for any even number n
1^{2} - 2^{2} + 3^{2} - 4^{2} + ... - n^{2} = (-1/2) n (n+1) |
The property is obvious for n = 2.
Now assume that the property is valid for n = k (with k an even number)
So, 1^{2} - 2^{2} + 3^{2} - 4^{2} + ... - k^{2} = (-1/2) k (k+1)
We have to prove that property is valid for n = k+2
We have to prove:
1^{2} - 2^{2} + 3^{2} - 4^{2} + ... - k^{2} + (k+1)^{2} - (k+2)^{2} = (-1/2)(k+2)(k+3)
Proof:
1^{2} - 2^{2} + 3^{2} - 4^{2} + ... - k^{2} + (k+1)^{2} - (k+2)^{2} = (1^{2} - 2^{2} + 3^{2} - 4^{2} + ... - k^{2}) + (k+1)^{2} - (k+2)^{2} = (-1/2) k (k+1) + ((k+1)^{2} - (k+2)^{2} ) We try to factor this expression = (-1/2) k (k+1) + ((k+1) -(k+2)).((k+1) + (k+2)) = (-1/2) k (k+1) + (-1) (2k + 3) = (-1/2) ( k(k+1) + 4k + 6) = (-1/2) ( k^{2} + 5k + 6 ) = (-1/2) (k + 2)(k + 3)
We will show that, in each box with n balls, all balls have equal size! |
The property is obvious for n = 1.
Now assume that the property is valid for n = k
So, in each box with k balls, all balls have equal size. (*)
Now take a box with k+1 balls.
On an arbitrary ball we write the letter A and on another randomly chosen ball
we write the letter B.
To show that all balls have equal size it is sufficient to prove
that the randomly selected balls A and B are equal in size.
Now we pick a ball, different from A and B, from the box. Now, the box contains k balls.
Relying on (*) we know that the k balls are equal in size. So, the balls A and B are equal in size.
Conclusion: In each box with n balls, all the balls are equal in size.
---------------------------
Explain exactly why this reasoning is wrong.
.