Question

Prove by Mathematical Induction? : `sum_(k=0)^n x^k = (1-x^(n+1)) / (1-x)`

Answer 1

We aim to prove by Mathematical Induction that for `n in NN, n ge 1` then:

`sum_(k=0)^n x^k = (1-x^(n+1)) / (1-x)`

When `n=1` the given result gives:

`LHS = sum_(k=0)^n x^k = x^0 + x^1 = 1 +x`
`RHS = (1-x^2)/(1-x) = ( (1+x)(1-x) ) / (1-x) = 1 + x`

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

Now, Let us assume that the given result 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=0)^m x^k = (1-x^(m+1)) / (1-x)`

Adding the next term of the sum gives us:

`sum_(k=0)^(m+1) x^k = (sum_(k=0)^(m) x^k ) + x^(m+1)`

And using the above assumption, we have:

`sum_(k=0)^(m+1) x^k = (1-x^(m+1)) / (1-x) + x^(m+1)`
`" " = (1-x^(m+1) + (1-x)x^(m+1))/(1-x)`
`" " = (1-x^(m+1) + x^(m+1) + x x^(m+1))/(1-x)`
`" " = (1 + x x^(m+1))/(1-x)`
`" " = (1 + x^(m+2))/(1-x)`
`" " = (1 + x^((m+1)+1))/(1-x)`

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

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

Hence, by the process of mathematical induction the given result is true for `n in NN, n ge 1` QED

Supporting Note

The above result should come as no surprise because:

`sum_(k=0)^n x^k = x^0+x^1+x^2 + ... + x^n`

Which are the `n+1` terms of a GP with:

First Term `a=x^0=1`,
Common Ratio `r=x`

And so, using the GP formula, the sum of the first `n` terms is given by:

`S_n = a(1-r^n)/(1-r)`
`\ \ \ \ = 1(1-x^(n+1))/(1-x) \ \ \ ` (remember we have `n+1` terms)
`\ \ \ \ = (1-x^(n+1))/(1-x)` QED