# [SOLVED] induction proof of summation

• Nov 30th 2009, 12:10 AM
jmedsy
[SOLVED] induction proof of summation
use mathematical induction to show that the summation from i=n to 2n-1 (2i+1) = 3n^2 whenever n is a nonnegative integer
• Nov 30th 2009, 12:40 AM
Jameson
Quote:

Originally Posted by jmedsy
use mathematical induction to show that the summation from i=n to 2n-1 (2i+1) = 3n^2 whenever n is a nonnegative integer

Let P(n) be the statement that $\displaystyle P(n)=\sum_{i=n}^{2n-1}2i+1=3n^2$, for all non-negative n. Assume that P(n) is true for some $\displaystyle n \le k$

$\displaystyle P(k+1)=\sum_{i=k+1}^{2(k+1)-1}2i+1$

The upper limit of the sum is also 2k+1. Think about how this second sum compares to the first.

$\displaystyle \sum_{i=k+1}^{2(k+1)-1}2i+1=\left(\sum_{i=k}^{2k-1}2i+1\right)-(2k+1)+(4k+1)+(4k+2+1)$

I'll let you figure out why P(k+1) can be written like that. What extra terms does it contain that P(k) does not?
• Nov 30th 2009, 02:29 AM
jmedsy
Quote:

Originally Posted by Jameson
Let P(n) be the statement that $\displaystyle P(n)=\sum_{i=n}^{2n-1}2i+1=3n^2$, for all non-negative n. Assume that P(n) is true for some $\displaystyle n \le k$

$\displaystyle P(k+1)=\sum_{i=k+1}^{2(k+1)-1}2i+1$

The upper limit of the sum is also 2k+1. Think about how this second sum compares to the first.

$\displaystyle \sum_{i=k+1}^{2(k+1)-1}2i+1=\left(\sum_{i=k}^{2k-1}2i+1\right)-(2k+1)+(4k+1)+(4k+2+1)$

I'll let you figure out why P(k+1) can be written like that. What extra terms does it contain that P(k) does not?

Thanks. Instead of using the appropriate arbitrary k, I've been using n+1 (which proves the proposition for the value sequentially after n, but not for all n). Anyway, the steps of this particular proof are clear now.