-1
$\begingroup$

This question already has an answer here:

if given a positive integer $n$ is the sum of the $n$ smallest odd numbers equal to $n^2$

|cite|improve this question
$\endgroup$

marked as duplicate by user147263, Fly by Night, Blue, achille hui, voldemort Aug 27 '14 at 0:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Base case: Prove/show/verify for $n=1$. Induction hypothesis: assume true for $n=k$. Step 3: Prove true for $n=k+1$. $\endgroup$ – paw88789 Aug 26 '14 at 23:13
  • $\begingroup$ It looks as if you want to show this: The sum of the $n$ smallest odd positive integers is equal tn^2$. Induction is one way to do it. $\endgroup$ – André Nicolas Aug 26 '14 at 23:13
  • $\begingroup$ @Andre N: Sum of $n$ smallest odd positive integers, I think. $\endgroup$ – paw88789 Aug 26 '14 at 23:15
  • $\begingroup$ Yes, forgot to write odd. You want to show that if the sum of the odds up to $2k-1$ is $k^2$, then the sum of the odds up to $2(k+1)-1$ is equal to $(k+1)^2$. This is easy, because $k^2+(2k+1)=(k+1)^2$. $\endgroup$ – André Nicolas Aug 26 '14 at 23:17
  • $\begingroup$ A few suggestions: (1) try to search before asking. Most standard induction questions have been asked and answered before. (2) Write a descriptive title for your question. This is for your own benefit: the system will suggest related posts based on title. (3) Use LaTeX. $\endgroup$ – user147263 Aug 26 '14 at 23:25
0
$\begingroup$

You want to show $1+3+\cdots+(2n-1)=n^2$. Note that $1+2+\cdots+2n=n(2n+1)$, and $2+4+\cdots+2n=2(1+2+\cdots+n)=n(n+1)$. Can you prove these two formulas? Your result now follows by subtraction.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @yeyee6512y: Let $S=1+2+\cdots+n$=$n+(n-1)+\cdots+1$. So, $2S=n(n+1)$. Or, prove this statement by induction. $\endgroup$ – voldemort Aug 26 '14 at 23:33
  • $\begingroup$ @yeyee6512y: Check that last step-it isn't correct. $k^2+2k-1+1=k^2+2k=k(k+2)$. $\endgroup$ – voldemort Aug 26 '14 at 23:38
  • $\begingroup$ @yeyee6512y: sorry- edited . $\endgroup$ – voldemort Aug 26 '14 at 23:41
  • $\begingroup$ by factoring :). $\endgroup$ – voldemort Aug 26 '14 at 23:43
  • $\begingroup$ It's not- you should check your computation :). All I am suggesting is that write $1+2+..n$ in one row, and write $n+(n-1)+..1$ in the next row, and add term by term- you will see a magic happen :). $\endgroup$ – voldemort Aug 26 '14 at 23:46
6
$\begingroup$

My favorite, the proof without words:

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Indeed. That is pretty sweet. $\endgroup$ – Graham Kemp Aug 26 '14 at 23:42
  • 1
    $\begingroup$ @GrahamKemp Thanks; does that get me an upvote? ;) $\endgroup$ – Ahaan S. Rungta Aug 26 '14 at 23:43
2
$\begingroup$

First we observe that the pattern seems to hold. $1^2 = 1, 2^2 = 1+3 , 3^2 = 1+3+5, \ldots$

Then we notice that this is: $2^2 = 1^2 + 3, 3^2=2^2 + 5, \ldots$ and we predict that: $$(n+1)^2 =\mathop{(n)^2 + \underbrace{(2(n+1)-1)}}_{\text{the }(n+1)^{th}\text{ odd number}}$$

For a proof by induction, $\require{cancel}\cancelto{\text{you}}{\text{we}}$ need to demonstrate that this is so for all positive integer $n$. (Having already established the base case: $n=1: 1^2=1$)

More formally: The steps in proof by induction are:

$$\begin{align} & \mathsf P(1) & \text{base case}\\ & \forall n\in\mathbb{Z}^+ : \mathsf P(n)\to \mathsf P(n+1) & \text{iterative case} \\ \therefore \quad & \forall n\in\mathbb{Z}^+ : \mathsf P(n) & \text{by induction}\end{align}$$

Our premise is: $\mathsf P(n):= (n^2=\sum_{k=1}^n (2n-1))$

Base case: $1^2= (2(1)-1) \quad\color{green}{\checkmark}$

Iterative case: $\Bigl(n^2 = \sum_{k=1}^n (2n-1))\implies \underbrace{(n+1)^2 = n^2 + (2(n+1)-1)}_{\text{show this is true for all }n\in\mathbb Z ^+}\Bigr) \quad \color{green}{?}$

Notes

The $k^{th}$ odd number is $2k-1$. As in: $1=2(1)-1, 3=2(2)-1, 5=2(3)-1, \ldots$.

Then the sum of the first $n$ odd numbers is: $a_n:=\sum_{k=1}^n (2k-1)$ $$\begin{align}a_n &:= 1+3+5+\cdots+(2n-1)\end{align}$$

It follows that the sum of the first $n+1$ odd numbers must be: $a_{n+1} = \sum_{k=1}^{n+1} (2k-1)$ $$\begin{align}a_{n+1}&:= 1+3+5+\cdots+(2 (n)-1)+(2 (n+1)-1)\end{align}$$

Hence by subtraction it is that: $a_{n+1} - a_{n} = (2(n+1)-1)$

Now if it is that: $a_n=(n)^2$ then it would also be that: $a_{n+1} = (n+1)^2$.

Thusly our induction step needs to show: $(n+1)^2 = (n)^2 + (2(n+1)-1)$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @yeyee6512y See the added notes. (Also, corrected a typo.) $\endgroup$ – Graham Kemp Aug 27 '14 at 0:46
  • $\begingroup$ @yeyee6512y Which step don't you follow? $\endgroup$ – Graham Kemp Aug 27 '14 at 0:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.