How Does Series Notation Equal the Highlighted Part in Induction Proof?

[Googl]

Hi all,

I am so sorry I don't know whether to post this. I am revising Proof by mathematical induction Further maths using an Edexcel FP1 book. The following is from chapter 6 example 3. I know how to work Proof by mathematical induction it is part of the example that I don't understand.

I don't know how the series notation becomes to equal to the highlighted part.

http://www.mathsrev.com/wp-content/uploads/Proof-by-mathematical-induction.png

The problem here is "r is a power" and I have not meant problems where r is a power and the book does not explain so much about that.

Thanks for the help.

 

[micromass]

Prove the equality by induction?

 

[Googl]

Sorry you're not helping me try to prove by induction. The image shows part of the work out. I understand how to prove it but I don't understand how the sum notation becomes to equal to the highlighted part.

I don't understand how the author got Ʃr2^r to equal to the highlighted part.

Thanks.

 

[micromass]

Can you post the entire paragraph and not just two equalities? I think I know what's going on now, but I need to see the entire paragraph first.

 

[Googl]

The question is;

Prove by the method of mathematical induction, that;

Ʃ r2^r = 2[1 + (n - 1)2ⁿ]

n = 1;

LHS = 1(2)¹ = 2

RHS = 2[1 + (1-1)2⁰] = 2

Assume that the summation formula is true for n = k.

n = k + 1;

http://www.mathsrev.com/wp-content/uploads/Proof-by-mathematical-induction.png
= 2 + 2(k-1)2^k + (k + 1)2^{k + 1}
= 2 + (k - 1)2^{k + 1} + (k + 1)2^{k + 1}
= 2 + (k - 1 + k + 1)2^{k + 1}
= 2 + 2k2^{k + 1}
= 2(1 + k2^{k + 1})
= 2[1 + ((k + 1) - 1)2^{k + 1}]

I left out some comments.

 

[micromass]

Right, so you assumed the summation formula was true for $k$. This means that you know that

$$\sum_{r=1}^k r2^r = 1(2^1) + ... + k2^k = 2(1+(k-1)2^k)$$

is true. Now you just substitute that in your formula.

 

[Googl]

Right, so you assumed the summation formula was true for $k$. This means that you know that

$$\sum_{r=1}^k r2^r = 1(2^1) + ... + k2^k = 2(1+(k-1)2^k)$$

is true. Now you just substitute that in your formula.

How does it come from;
$$1(2^1) + ... + k2^k$$

...to...

$$2(1+(k-1)2^k)$$

That is what I don't understand.

 

[micromass]

You want to prove the formula Ʃ r2r = 2[1 + (n - 1)2n].

By induction hypothesis, you assume that the formula is true for n=k.

 

[Zatman]

I think I see what you're getting confused at. It's the way this line is written:

∑r2^r = 1(2¹) + 2(2²) + 3(2³) + ... + k(2^k) = 2(1+(k-1)2^k)

The far LHS is the original summation you're interested in.

The 'middle side' is just the LHS written out in full.

The far RHS is your assumption. You are assuming that when n=k the original formula for the summation works, so you substitute k into

2(1+(n-1)sⁿ)

 

[pbuk]

I see your problem; I think it would be clearer to write the first line that you highlighted $$\sum_{r=1}^{k+1} r2^r = \sum_{r=1}^k r2^r + (k+1)2^{k+1}$$ then it is clear that the next line follows by substitution of the hypothesised summation formula.

 

[Googl]

I understand how to prove it.

What I don't understand is this part.

$$1(2^1) + ... + k2^k = 2(1+(k-1)2^k)$$

Please explain how this: $$1(2^1) + ... + k2^k$$

... is equal to this: $$2(1+(k-1)2^k)$$

I know there are formulas you can use but I have not used them before for when r is a power of a number.

$$1(2^1) + ... + k2^k$$
...there is something missing here between these lines and that is what I am trying to understand.
$$2(1+(k-1)2^k)$$

I know how to prove it by mathematical induction

 

[Googl]

I see your problem; I think it would be clearer to write the first line that you highlighted $$\sum_{r=1}^{k+1} r2^r = \sum_{r=1}^k r2^r + (k+1)2^{k+1}$$ then it is clear that the next line follows by substitution of the hypothesised summation formula.

Thanks. That is what I had not realized. I understand that now.

Is there a way to find the following without knowing the RHS expression? ...because they and you have used the RHS after assuming that n = k.
$$\sum_{r=1}^{k+1} r2^r$$

I have only been revising Proof by mathematical induction for two days now so everything is coming together. I have don't know how to find the sum when r is a power as above. Is there some examples that you know online?

 

[pbuk]

I'm not sure exactly what you mean, but if you are asking whether you can do a proof by induction without knowing what the expression you are trying to prove is, the answer is no. That is why you are always given a proposition to prove.

Don't get hung up about the fact that there are powers in there, just work through the steps: until you have fully grasped the concept of proof by induction you might find it helps to look at this in abstract terms:

• We are given a proposition $p(n)$ In this case the proposition is $$\sum_{r=1}^n f(r) = S(n)$$
• We show that if $p(k)$ is true then $p(k+1)$ is also true. In this case, we do it thus: $$\begin{align} \sum_{r=1}^{k+1} f(r) &= \sum_{r=1}^{k} f(r) + f(k+1) \rm{\ \ (by \ \ definition)} \\ &= S(k) + f(k+1) \rm{\ \ (from \ \ the \ \ proposition)} \end{align}$$ We then expand $S(k) + f(k+1)$ and rearrange terms, showing that this is identical to $S(k+1)$. There is no fancy expansion of power series, all this is achieved simply by multiplying out the brackets and noting that $2^{k+1} = 2(2^k)$ etc.
• We show that for some particular $n = m$, $p(m)$ is true.

 

[Googl]

Thanks a lot that helped. On a side note (forgetting the Proof by 'mathematical induction' part) how might you find an expression for the following ie a general formula where k is an integer.

$$\sum_{r=1}^{k} r2^r$$

or

$$\sum_{r=1}^{k} 2^r$$

I understand the Proof by 'mathematical induction' part now.

 

[pbuk]

Trial and error. You might start by inspecting a few terms of the series, looking at first and higher order differences and comparing them with expressions that are likely to grow at a similar rate. Try it with $\sum_{r=1}^{k} 2^r$, once you get to the 6th term they should start to remind you of something.