6
$\begingroup$

Here is what I have so far:

The $n$th odd number is $2n-1$.

So we prove that $1+3+...+(2n-3)+(2n-1)= n^2$.

Separate the last term and you get: $[1+3+...+(2n-3)]+(2n-1)$

$[1+3+...+(2n-3)]$ is the sum of the first $(n-1)$ odd numbers.

Here is where I get stuck. The textbook says that the sum of the first $(n-1)$ odd numbers is $(n-1)^2$, but why is that the case? It seems like a recursive explanation because we are trying to prove that the sum of the first $n$ odd numbers is $n^2$. Since we have not yet proved that, how can one say with certainty that the sum of the first $(n-1)$ odd numbers is $(n-1)^2$ ?

$\endgroup$
5
  • 7
    $\begingroup$ This is mathematical induction. $\endgroup$ – Henricus V. Feb 21 '16 at 20:33
  • $\begingroup$ The way I read this is that you are asking why we may assume that the sum of the first $(n - 1)$ odd numbers is $(n - 1)^2$. Is that correct? $\endgroup$ – N. F. Taussig Feb 21 '16 at 20:59
  • $\begingroup$ The picture here is quite nice: en.wikipedia.org/wiki/Proof_without_words#Sum_of_odd_numbers $\endgroup$ – user940 Feb 21 '16 at 21:04
  • 1
    $\begingroup$ Two related questions. $\endgroup$ – Lucian Feb 22 '16 at 1:17
  • $\begingroup$ It seems that your problem is more with the question why mathematical induction works rather than with this particular proof. Maybe you can have a look at this post (and perhaps also some of the posts linked there might help you.) $\endgroup$ – Martin Sleziak Feb 22 '16 at 14:23
16
$\begingroup$

Here is a proof without words:

enter image description here

$\endgroup$
0
2
$\begingroup$

Assume that the statement is not true.

Then a smallest odd number $2n-1$ must exist with $1+\cdots+(2n-1)\neq n^2$.

Based on $2\cdot1-1=1^2$ we conclude that $n>1$.

However, then we find: $$1+\cdots+(2n-3)+(2n-1)=(n-1)^2+(2n-1)=n^2$$

That means that we found a contradiction and our conclusion is that our assumption (i.e. "the statement is not true") must be incorrect.

Final conclusion: the statement is true.

$\endgroup$
2
  • 1
    $\begingroup$ Shouldn't you also talk about the fact that the statement is true for $n=1$? $\endgroup$ – AlohaSine Feb 21 '16 at 21:13
  • $\begingroup$ @MathematicsStudent1122 Yes, for completeness it must be stated that $1=1^2$ so that $n>1$. I repaired. Thank you. $\endgroup$ – drhab Feb 21 '16 at 21:18
2
$\begingroup$

Another way of looking at is ...

$$\begin{align}&1 + 3 + 5 + {\dots} + 2n - 1 \\ &= (n - (n - 1)) + {\dots} + (n - 4) + (n - 2) + n + (n + 2) + (n + 4) + {\dots} + (n + n - 1)\\ &= n + n +n + {\dots} +n (n times)\\ &= n^{2}\end{align}$$

It can also be proved with the sum of arithmetic progression. The sum of an $A.P.$ with $n$ terms, difference $d$, and initial term $a$.

$$\begin{align}T_1 &=a\\ T_2 &=a + 2d\\ .\\ .\\ .\\ T_n &= a + (n-1)d\end{align}$$

Adding all these terms,

$$\begin{align}S &= na + d(1+2+{\dots}+n-1)\\ S &= na + \frac{n(n-1)d}{2}\\ S &= \frac{n}{2}(a + a + (n-1)d)\\ S &= \frac{n}{2}(a + T_n)\end{align}$$

Applying this to our series,

$$\begin{align}S &= \frac{n}{2}(1+2n - 1)\\ S &= n^{2}\end{align}$$

This property of odd numbers was used to generate Pythagorean triplets by Fibonacci. $1$. Pick an odd number and square it. The number chosen in $m$.

$2$. $m^2$ also lies in the series. Take the sum of all odd numbers before $m^2$. It is $(\frac{(m^2-1)}{2})^2$

$3$. Adding these two numbers will also be a perfect square. $m^2 +(\frac{m^2-1}{2})^2 = \frac{m^4 +2m^2+ 1}{4} = (\frac{m^2 + 1}{2})^2$

The numbers, $m, \frac{m^2-1}{2}, \frac{m^2+1}{2}$ are a Pythagorean triplet, wherever m is odd.

$\endgroup$
1
$\begingroup$

The proof consists of two steps:

$1.$ The basis (base case): prove that the statement holds for the first natural number $n$. Usually, $n = 0$ or $n = 1$, rarely, $n = –1$ (although not a natural number, the extension of the natural numbers to $–1$

$2.$ The inductive step: prove that, if the statement holds for some natural number $n$, then the statement holds for $n + 1$. The hypothesis in the inductive step that the statement holds for some n is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for $n + 1$.

Whether $n = 0$ or $n = 1$ depends on the definition of the natural numbers. If $0$ is considered a natural number, as is common in the fields of combinatorics and mathematical logic, the base case is given by $n = 0$. If, on the other hand, $1$ is taken as the first natural number, then the base case is given by $n = 1$.

$\endgroup$
2
  • $\begingroup$ The question seems to be why we can make the induction assumption that $$\sum_{k = 1}^{n -1} (2k - 1) = (n - 1)^2$$ $\endgroup$ – N. F. Taussig Feb 21 '16 at 20:45
  • 1
    $\begingroup$ @N.F.Taussig Ok, this is the inductive step , assume that... $\endgroup$ – 3SAT Feb 21 '16 at 20:54
1
$\begingroup$

Hint:

If you want justify the inductive assumption than note that the sum $$ 1+3+5+\cdots +(2n-5)+(2n-3)+(2n-1) $$ can be reordered as $$ (1+(2n-1))+(3+(2n-3))+(5+(2n-5)) \cdots= 2n +2n +\cdots $$ and counts the number of the $2n$ terms in the final sum ( with a bit of care when $n$ is odd).

$\endgroup$
0
$\begingroup$

We have $$\sum_{i=1}^n 2i-1 = 2\sum_{i=1}^n i - n = n(n+1) - n = n^2 $$

Edit: To respond to your point, the textbook is using something known as "mathematical induction". The idea is, simply, that you are allowed to assume a particular statement is true for the case $n-1$. If the statement is true for a particular base case, and it being true for $n-1$ implies that it is true for $n$, it true for all natural numbers.

Think of it like an infinite number dominoes falling. If one domino falls, the subsequent one does as well. Hence we simply need to make the first domino fall to make every one of the dominoes fall.

$\endgroup$
3
  • $\begingroup$ The question seems to be why we can make the induction assumption that $$\sum_{k = 1}^{n -1} (2k - 1) = (n - 1)^2$$ $\endgroup$ – N. F. Taussig Feb 21 '16 at 20:45
  • $\begingroup$ Are you factoring the 2 out of 2i-1? shouldn't it be 2(i-1/2)? $\endgroup$ – Nicholas Cousar Feb 21 '16 at 20:55
  • $\begingroup$ @NicholasCousar No. The lack of brackets make it somewhat obscure. The $-n$ in the second equation is separate from the sum. I split it. $\endgroup$ – AlohaSine Feb 21 '16 at 21:09
0
$\begingroup$

You can solve this question simply by using the formula for an arithmetic series. the formula is n(2a+(n-1)d)/2 By simply plugging in the values you get. n(2x1+(n-1)2)/2 Now you get. n(2n-2+2)/2 Now it is 2n(n)/2 2n^2/2 = n^2 Hence Proved.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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