# Math Help - Basic Proof by Induction

1. ## Basic Proof by Induction

Hi,

im a bit stuck on an question,

using proof by induction, prove that

sum_(r=1)^n(2 r-1) = n^2

same formula formatted:
http://www.wolframalpha.com/input/?i=Sum[2+r+-+1%2C+{r%2C+1%2C+n}]

2. ## Re: Basic Proof by Induction

Originally Posted by nomanslan
using proof by induction, prove that
sum_(r=1)^n(2 r-1) = n^2
If n=1 then $2\cdot 1-1=1^2$ so base case it true.

Suppose that $N>1$ and $\sum\limits_{r = 1}^N {\left( {2r - 1} \right)} = N^2$ is true.

Then look at $\sum\limits_{r = 1}^{N+1} {\left( {2r - 1} \right)} =\sum\limits_{r = 1}^N {\left( {2r - 1} \right)}+[2(N+1)-1]$

Can you finish?

3. ## Re: Basic Proof by Induction

Ok so we want to show that
$\sum_{r=1}^n (2r-1) = n^2$

to prove by induction we need to show for the base case (n=1) in this case we have
$\sum_{r=1}^1 (2r-1) = 1 = 1^2$
so it is true in that case,

now for the inductive step we want to show that given that
$\sum_{r=1}^k (2r-1) = k^2$

then
$\sum_{r=1}^{k+1} (2r-1) = (k+1)^2$

so write it out and split the sum like so
$\sum_{r=1}^{k+1} (2r-1) = \sum_{r=1}^{k} (2r-1) + (2(k+1) - 1) = k^2 + 2k +1$

Give it a go from there

4. ## Re: Basic Proof by Induction

s(k+1) = s(k) +t(k) + 1
= k^2+(2(k+1)-1)+1 = k^2+2k+1

therefore
2r=1 = n^2?

5. ## Re: Basic Proof by Induction

Originally Posted by nomanslan
s(k+1) = s(k) +t(k) + 1
= k^2+(2(k+1)-1)+1 = k^2+2k+1

therefore
2r=1 = n^2?
That makes no sense. There is no "r" or "n" in what you have above.

The point was supposed to be that k^2+ 2k+ 1= (k+ 1)^2.

6. ## Re: Basic Proof by Induction

Originally Posted by nomanslan
Hi,

im a bit stuck on an question,

using proof by induction, prove that

sum_(r=1)^n(2 r-1) = n^2

same formula formatted:
http://www.wolframalpha.com/input/?i=Sum[2+r+-+1%2C+{r%2C+1%2C+n}]

\displaystyle \begin{align*} \sum_{r = 1}^n{\left(2r - 1\right)} &= 2\sum_{r = 1}^n{r} - \sum_{r = 1}^n{1} \\ &= 2 \cdot \frac{n(n + 1)}{2} - n \\ &= n(n + 1) - n \\ &= n^2 + n - n \\ &= n^2 \end{align*}
And in case you weren't sure that \displaystyle \begin{align*} \sum_{r = 1}^n{r} = \frac{n(n + 1)}{2} \end{align*}...