Question

Can you prove this using mathematical induction?

#1/2+2/(2^2)+3/(2^2)+...+n/(2^n)=2- (n+2)/(2^n)#

Answer 1

What you need to do is:
1) prove that it holds for `n=1`
2) prove that, if it holds for `n-1`, then it holds for `n`, where `n>1`

Explanation:

1) the first statement is easy to check, we just need to use `n=1`. Doing so, we have `1/2 = 2 - (1+2)/2^1 = 2-3/2 = 1/2`, which is true.

2) now, for the second statement, let's suppose it holds for `n-1`. If so, we have `1/2 + ... + (n-1)/2^(n-1) = 2 - ((n-1)+2)/2^(n-1)`.

Therefore, `1/2 + ... + (n-1)/2^(n-1) + n/2^n = 2 - ((n-1)+2)/2^(n-1) + n/2^n`, but we can rewrite the right hand side as

`2 - ((n-1)+2)/2^(n-1) + n/2^n = 2 - (2(n-1)+2*2-n)/2^n =`

`2 - (2*n-2+4-n)/2^n = 2 - (n+2)/2^n`//

So, by the Induction Principle, the equation holds for any `n>=1`

Hope it helps.

Answer 2

I assume there is an error in the given sum and the `3^(rd)` term should in fact read `3/2^3` rather than `3/2^2`

Induction Proof - Hypothesis

We seek to prove that:

`1/2 + 2/2^2 + 3/2^3 + ... + n/2^n = 2-(n+2)/2^n`

Which can also be written as:

`sum_(k=1)^n \ k/2^k = 2-(n+2)/2^n` ..... [A]

So let us test this assertion using Mathematical Induction:

Induction Proof - Base case:

We will show that the given result, [A], holds for `n=1`

When `n=1` the given result gives:

`LHS = sum_(k=1)^1 \ k/2^k = 1/2^1=1/2`
`RHS = 1(4-1)/3 = 2-(1+2)/2^1 = 2-3/2 1/2`

So the given result is true when `n=1`.

Induction Proof - General Case

Now, Let us assume that the given result [A] is true when `n=m`, for some `m in NN, m gt 1`, in which case for this particular value of `m` we have:

`sum_(k=1)^m \ k/2^k = 2-(m+2)/2^m` ..... [B]

Consider the LHS of [A] with the addition of the next term, in which case we have

`LHS = sum_(k=1)^(m+1) \ k/2^k`
`\ \ \ \ \ \ \ \ = (sum_(k=1)^(m) \ k/2^k) + (m+1)/2^(m+1)`
`\ \ \ \ \ \ \ \ = 2-(m+2)/2^m + (m+1)/2^(m+1) \ \ \` using [B]
`\ \ \ \ \ \ \ \ = 2 - (2(m+2))/(2 * 2^m) + (m+1)/2^(m+1)`
`\ \ \ \ \ \ \ \ = 2 - (2m+4)/(2^(m+1)) + (m+1)/2^(m+1)`
`\ \ \ \ \ \ \ \ = 2 - ((2m+4)-(m+1))/(2^(m+1))`
`\ \ \ \ \ \ \ \ = 2 - ((2m+4-m-1))/(2^(m+1))`
`\ \ \ \ \ \ \ \ = 2 - (m+3)/(2^(m+1))`
`\ \ \ \ \ \ \ \ = 2 - ((m+1)+2)/(2^(m+1))`

Which is the given result [A] with `n=m+1`

Induction Proof - Summary

So, we have shown that if the given result [A] is true for `n=m`, then it is also true for `n=m+1` where `m gt 1`. But we initially showed that the given result was true for `n=1` so it must also be true for `n=2, n=3, n=4, ...` and so on.

Induction Proof - Conclusion

Then, by the process of mathematical induction the given result [A] is true for `n in NN`

Hence we have:

`1/2 + 2/2^2 + 3/2^3 + ... + n/2^n = 2-(n+2)/2^n` QED