Another Induction Q (1 Viewer)

[Sparcod]

HSC Question

1+2+4+...+2^(n-1) = 2^n -1
LHS to the power of n+1 RHS 2 to power of n

Thanks to anyone who helps.

 

[insert-username]

1+2+4+...+2^(n-1) = 2ⁿ - 1


Step 1. Prove for n = 1 (smallest n)

LHS = 1
RHS = 1

I.e. true for smallest n.


Step 2. Assume true for n = k, i.e.

1+2+4+...+2^(k-1) = 2^k - 1


Step 3. Prove true for n = k+1, i.e.

1+2+4+...+2^(k-1) + 2^k = 2^k+1 - 1

LHS = 2^k - 1 + 2^k (since, from assumption, 1+2+4+...+2^(k-1) = 2^k - 1)

= 2.2^k - 1

RHS = 2^k+1 - 1

= 2.2^k - 1 (whenever you have something to the power of k+1, you're multiplying it once more by the base)

= LHS, i.e. true for n = k+1 if true for n = k.


Therefore, since true for n=1, and true for n=k+1 if true for n=k, then true for n=2, n=3, etc.


I_F

 

[Sparcod]

Thanks. Isnt this an arithmetic progression?

BTW for arithmetic series you use T (k+1) + S (k) = S (k+1) dont you?

 

[insert-username]

This is a geometric series with common ratio 2, since the variable is in the exponent. However, if you are asked to prove through mathematical induction, then you cannot use the series formula. You must use the induction process or you get nothing.


BTW for arithmetic series you use T (k+1) + S (k) = S (k+1) dont you?

Yes, the sum of (k+1) terms of an arithmetic series is equal to the sum of k terms plus the (k+1)th term.


I_F

 

[Sparcod]

Thanks buddy. I learnt something. exponentials mean that the base number is the common ratio.

 

[insert-username]

No problemo.


I_F

 

[Sparcod]

Step 3. Prove true for n = k+1, i.e.

1+2+4+...+2^(k-1) + 2^k = 2^k+1 - 1


I_F

Don't get the part 2^k. Where did it come from?

 

[pLuvia]

He substituted 2^n-1, n = k+1 hence the 2^k

 

[insert-username]

We have assumed that the statement is true for n=k (1+2+4+...+2^(k-1) = 2^k - 1). To prove true for n=k+1, you then have to add 2^(k-1+1), i.e. 2^k, to the left hand side, since the statement is a sum of terms and the (k+1)th term is 2^(k-1+1).

I_F

 

[Riviet]

A neater way of doing the LHS=RHS bit is when you get to the line 2.2^k-1 , you can just bring the 2 up to the index to get 2^k+1-1, and that equals the LHS. No need to go to right hand side and back to left.