Name: Tabius
Who is asking: Student
Level: Secondary
Question:
Use mathematical induction to prove that the following formulae are true for all positive integers:
a) 1 + 3 + 5+...+(2n - 1) = n^{ 2}
b) 2^{ n} > n.
Hi Tabius,
With induction proofs there are two steps. You need to get started and you need to keep going.
Let's look at your first problem. The statement to be proved is
1 + 3 + 5+...+(2n - 1) = n^{ 2}
To get started you need to verify that the statement is true for the smallest value of n, in your problem this is n = 1. When n = 1 the left side is 1 and the right side is 1^{ 2} = 1. Thus the statement is true.
At this stage I always do some more arithmetic just to check that the statement "seems" true. It is not part of the proof, just for my own satisfaction. When n = 2 the left side is 1 + 3 = 4 and the right side is 2^{ 2} = 4, so the statement is true. Check yourself when n = 3.
To keep going you need to show that whenever the staement is true for some integer n it is also true for the next integer n + 1. Hence assume that the statement is true for the integer n, that is
Assumption
1 + 3 + 5 +...+ (2n - 1) = n^{ 2}
Using this assumption, what remains is to prove that the statement is true for the integer n + 1.