Subject: problem of induction Name: Zamira Who are you: Student (All) hi, i'm studying induction but i don't get how to proof that 1+2+2^2+2^3+...+2^(n-1) = (2^n) - 1. if you could help i really would appreciate it. zamira Hi Zamira, I want to state the problem more precisely. Prove that 1+2+22+23+...+2n-1 = 2n - 1 for n = 1, 2, 3, ... There are two steps in a proof by induction, first you need to show that the result is true for the smallest value on n, in this case n = 1. When n = 1 the left side has only one term, 2n-1 = 21-1 = 20 = 1. The right side is 2n - 1= 21 - 1 = 1. Thus the statement is true for n = 1. The second step is the inductive step. You need to show that if the statement is true for any particular value of n it is also true for the next value of n. If you can do this then, since it is true for n = 1 it will also be true for the next value of n, n = 2. Then, since it is true for n = 2 it will also be true for n = 3, and so on. To show the inductive step I am going to assume that the statement is true for the particular value of n, n = k. Here is my proof. Suppose that the statement is true for n = k, that is 1+2+22+23+...+2k-1 = 2k - 1           equation 1 I need to prove that the statement is true for n = k + 1, that is I need to prove that 1+2+22+23+...+2(k+1)-1 = 2k+1 - 1                equation 2 The left side of equation 2 is 1+2+22+23+...+2(k+1)-1 = 1+2+22+23+...+2k  The next to the last term in this sum is 2k-1 and hence I can write the left side of equation 2 as 1+2+22+23+...+2k-1 + 2k But I know that 1+2+22+23+...+2k-1 = 2k - 1 (this is equation 1) so the left side of equation 2 is is 1+2+22+23+...+2k-1 + 2k = 2k - 1 + 2k = 2(2k) - 1 = 2k+1- 1 Hence we have shown that the left side and right side of equation 2 are equal. This completes the inductive step and hence, by induction, I have proved that 1+2+22+23+...+2n-1 = 2n - 1 for n = 1, 2, 3, ... Penny