Tag: Sums

Prove that the sum of odd numbers is a perfect square

by RoRi

July 5, 2015

Prove $\displaystyle{\sum_{k=1}^n (2k-1) = n^2}.$

Proof. We write, $2k - 1 = k^2 - (k^2 - 2k +1) = k^2 - (k-1)^2$ which gives us a telescoping sum,

$\begin{align*} \sum_{k=1}^n (2k-1) &= \sum_{k=1}^n (k^2 - (k-1)^2) \\ &= n^2 - 0 & (\text{Telescoping property}). \\ &= n^2. \qquad \blacksquare \end{align*}$

Prove that the sum of 1’s from 1 to n equals n

by RoRi

July 4, 2015

Prove: $\displaystyle{\sum_{k=1}^n 1 = n}.$

Proof. We prove by induction. If $n = 1$ , then the statement is true since $\sum_{k=1}^1 1 = 1$ . Assume then that the statement is true for some $n = m \in \mathbb{Z}_{>0}$ . So,

$\sum_{k=1}^m 1 = m \quad \implies \quad \left( \sum_{k=1}^m 1 \right) + 1 = m+1 \quad \implies \quad \sum_{k=1}^{m+1} 1 = m+1.$

Where the final step follows since the value of 1 for $k = m +1$ is still 1. (Maybe this could confuse since we are summing over the index $k$ , but the value is independent of $k$ . So, really, we are just counting… so for each $k$ in the index we add 1; thus, when we have the sum from $k = 1$ to $m$ and add 1, it is the same as summing from $k = 1$ to $m+1$ ). Thus, by induction, the statement is true for all $n \in \mathbb{Z}_{> 0}. \qquad \blacksquare$

Prove some properties of finite sums

by RoRi

July 4, 2015

Prove the additive property of finite sums.
Prove the homogeneous property of finite sums.
Prove the telescoping property of finite sums.

(Note: Before we start these, I’ll note that these are all finite sums, so we are free to manipulate them in ways we can’t manipulate infinite sums. Which is to say, we can freely reorder terms in any way we like, or basically use our usual field axioms to put things in the form we want. If the sums are infinite (see chapters 10 and 11… or a course in real analysis) then we don’t have such freedom.)

Proof. We expand, rearrange, and then write back in summation notation,

$\begin{align*} \sum_{k=1}^n (a_k + b_k) &= (a_1 + b_1) + (a_2 + b_2) + \cdots + (a_n + b_n) \\ &= (a_1 + a_2 + \cdots + a_n) + (b_1 + b_2 + \cdots + b_n) & (\text{Assoc. and Comm.}) \\ &= \sum_{k=1}^n a_k + \sum_{k=1}^n b_k. \qquad \blacksquare \end{align*}$
Proof. We compute using the distributive law,

$\sum_{k=1}^n (ca_k) = ca_1 + ca_2 + \cdots + ca_n = c(a_1 + a_2 + \cdots + a_n) = c \sum_{k=1}^n a_k. \qquad \blacksquare$
Proof.

$\begin{align*} \sum_{k=1}^n (a_k - a_{k-1}) &= \left(\sum_{k=1}^n a_k\right) + (-1)\cdot \left( \sum_{k=1}^n a_{k-1}\right) & (\text{Parts (a) and (b)})\\ &= a_n + \sum_{k=1}^{n-1} a_k - \sum_{k=0}^{n-1} a_k & (\text{Reindexing the second sum}) \\ &= a_n + \sum_{k=1}^{n-1} a_k - a_0 - \sum_{k=1}^{n-1} a_k & (\text{Pulling out } a_0)\\ &= a_n - a_0. \qquad \blacksquare \end{align*}$

Evaluate some finite sums

by RoRi

July 4, 2015

$\displaystyle{\sum_{k=1}^4 k = 1 + 2 + 3 + 4 = 10}.$
$\displaystyle{\sum_{n=2}^5 2^{n-2} = 2^0 + 2^1 + 2^2 + 2^3 = 1 + 2 + 4 + 8 = 15}.$
$\displaystyle{\sum_{r=0}^3 2^{2r+1} = 2^1 + 2^3 + 2^5 + 2^7 = 2 + 8 + 32 + 128 = 170}.$
$\displaystyle{\sum_{n=1}^4 n^n = 1^1 + 2^2 + 3^3 + 4^4 = 1 + 4 + 27 + 256 = 288}.$
$\displaystyle{\sum_{i=0}^5 (2i+1) = 1 + 3 + 5 + 7 + 9 + 11 = 36}.$
$\displaystyle{\sum_{k=1}^5 \frac{1}{k(k+1)} = \frac{1}{2} + \frac{1}{6} + \frac{1}{12} + \frac{1}{20} + \frac{1}{30} = \frac{5}{6}}.$

Establish a formula for the sum of the reciprocals of the powers of 2

by RoRi

July 2, 2015

Claim:

$1 + \frac{1}{2} + \cdots + \frac{1}{2^n} = 2 - \frac{1}{2^n}.$

Proof. For $n = 0$ , on the left we have 1 and on the right we have $2 - \frac{1}{2^0} = 2-1 = 1$ . Thus, the formula holds for the case $n = 0$ .
Assume then that the formula is true for some $k = n \in \mathbb{Z}_{\geq 0}$ . Then,

$\begin{align*} && 1 + \frac{1}{2} + \cdots + \frac{1}{2^k} &= 2 - \frac{1}{2^k} & (\text{Ind. Hyp.}) \\ \implies && 1 + \frac{1}{2} + \cdots + \frac{1}{2^k} + \frac{1}{2^{k+1}} &= 2 - \frac{1}{2^k} + \frac{1}{2^{k+1}} & (\text{Adding } \frac{1}{2^{k+1}}) \\ \implies && 1 + \frac{1}{2} + \cdots + \frac{1}{2^{k+1}} &= 2 - \frac{2 - 1}{2^{k+1}} \\ \implies && 1 + \frac{1}{2} + \cdots + \frac{1}{2^{k+1}} &= 2 - \frac{1}{2^{k+1}}. \end{align*}$

Hence, if the statement is true for $k$ , then it is true for $k+1$ . Since we have established that it is true for $n = 0$ , we then have that it is true for all $n \in \mathbb{Z}_{\geq 0}. \qquad \blacksquare$

Establish a formula for alternating sum of squares

by RoRi

July 2, 2015

Claim:

$1 - 4 + 9 - 16 + \cdots + (-1)^{n+1} n^2 = (-1)^{n+1}(1+ \cdots +n)$

Proof. For $n =1$ , we have 1 on the left, and on the right $(-1)^2 (1) = 1$ . Thus, the formula is true for $n =1$ .
Assume then that it is true for some $n =k \in \mathbb{Z}_{>0}$ . Then,

$\begin{align*} 1-4+9- \cdots + (-1)^{k+1}k^2 &= (-1)^{k+1} (1+ \cdots +k) \\ \implies 1 + \cdots + (-1)^{k+2}(k+1)^2 &= (-1)^{k+1} (1+ \cdots + k) + (-1)^{k+2}(k+1)^2 &(\text{Adding } (-1)^{k+2}(k+1)^2) \\ &= (-1)^{k+2} \left(\frac{-k(k+1)}{2} \right) + (-1)^{k+2} (k+1)^2 \\ &= (-1)^{k+2} \left( k^2 + 2k +1 - \frac{k^2 + k}{2} \right) \\ &= (-1)^{k+2} \left( \frac{k^2}{2} + \frac{3k}{2} + 1 \right) \\ &= (-1)^{k+2} \left( \frac{(k+1)(k+2)}{2} \right) \\ &= (-1)^{k+2} (1+ \cdots + (k+1)) & (\text{I.4.4, Exercise #1 (a)}). \end{align*}$

Thus, if the formula is true for $k$ then it is true for $k+1$ . Since we established it is true for $n=1$ , we have that it is true for all $n \in \mathbb{Z}_{>0}. \qquad \blacksquare$

Prove some formulas using mathematical induction

by RoRi

July 2, 2015

Use mathematical induction to prove the following:

$\displaystyle{1+2+3+ \cdots + n = \frac{n(n+1)}{2}}.$
$\displaystyle{1+3+5+ \cdots + (2n-1) = n^2}.$
$\displaystyle{1^3 + 2^3 + 3^3 + \cdots + n^3 = (1+2+3 + \cdots + n)^2}.$
$\displaystyle{1^3+2^3+ \cdots +(n-1)^3 < \frac{n^4}{4} < 1^3 + 2^3 + \cdots + n^3}.$

Proof. The statement is true for $n = 1$ since on the left we have $1$ and on the right, $1(1+1)/2 = 1$ .
Assume then that the statement is true for $n=k \in \mathbb{Z}_{>0}$ . Then,

$\begin{align*} &&1+2+\cdots+k &= \frac{k(k+1)}{2} & (\text{Ind. Hyp.}) \\ \implies && 1+2+ \cdots + k + (k+1) &= \frac{k(k+1)}{2} + (k+1) & (\text{Adding } k+1 \text{ to both sides}) \\ \implies && 1+2 + \cdots + (k+1) &= \frac{k^2+3k+2}{2}\\ &&&= \frac{(k+1)(k+2)}{2}. \end{align*}$

Hence, if the statement is true for $k$ , then it is true for $k+1$ . Thus, since we have shown it is true for $n=1$ , we have the statement is true for all $n \in \mathbb{Z}_{>0}. \qquad \blacksquare$
Proof. The statement is true for $n=1$ since on the left we have $1$ and on the right, $1^2 =1$ .
Assume then that the statement is true for $n =k \in \mathbb{Z}_{>0}$ . Then,

$\begin{align*} && 1+3+5 + \cdots + (2k-1) &= k^2 & (\text{Ind. Hyp.}) \\ \implies && 1+3+5 + \cdots + (2k-1) + (2(k+1)-1) &= k^2 + 2(k+1) -1 & (\text{Adding } 2(k+1)-1)\\ \implies && 1+3+5 + \cdots + (2k-1) + (2k+1) &= k^2 + 2k + 1 \\ &&& = (k+1)^2. \end{align*}$

Hence, if the statement is true for $k$ , then it is true for $k+1$ . Thus, since we have shown it is true for $n=1$ , we have the statement is true for all $n \in \mathbb{Z}_{>0}. \qquad \blacksquare$
Proof. The statement is true for $n =1$ since on the left we have $1^3 = 1$ and on the right, $1^2 = 1$ .
Assume then that the statement is true for $n = k \in \mathbb{Z}_{>0}$ . Then,

$\begin{align*} && 1^2 + 2^3 + \cdots + k^3 &= (1+2 + \cdots + k)^2 & (\text{Ind. Hyp.}) \\ \implies && 1^3 + 2^3 + \cdots + k^3 &= \left (\frac{k(k+1)}{2} \right)^2 & (\text{Part (a)})\\ \implies && 1^3 + 2^3 + \cdots + k^3 + (k+1)^3 &= \left( \frac{k(k+1)}{2}\right)^2 + (k+1)^3 & (\text{Adding } (k+1)^3)\\ &&& = \frac{1}{4} (k^4 + 2k^3 + k^2) + (k^3 + 3k^2 + 3k + 1) \\ &&& = \frac{1}{4} (k^4 + 2k^3 + k^2 + 4k^3 + 12k^2 + 12k + 4) \\ &&& = \frac{1}{4} ((k+1)^2(k+2)^2) \\ &&& = \left( \frac{(k+1)(k+2)}{2} \right)^2 \\ &&& = (1 + 2 + \cdots + (k+1))^2 & (\text{Part (a)}) \end{align*}$

Hence, if the statement is true for $k$ , then it is true for $k+1$ . Thus, since we have shown it is true for $n=1$ , we have the statement is true for all $n \in \mathbb{Z}_{>0}. \qquad \blacksquare$
Proof. The statement is true for $n = 1$ since the term on the left is $0^3 = 0$ , the term in the middle is $1^4 / 4 = 1/4$ , and the term on the right is $1^3 = 1$ . Since $0 < \frac{1}{4} < 1$ , the statement is indeed true for $n =1$ .
Assume then that the statement is true for some $n =k \in \mathbb{Z}_{>0}$ . Then, the induction hypothesis gives us,

$1^3 + 2^3 + \cdots + (k-1)^3 < \frac{k^4}{4} < 1^3 + 2^3 + \cdots + k^3.$

Taking the left inequality first, we have

$\begin{align*} && 1^3 + \cdots + (k-1)^3 &< \frac{k^4}{4} \\ \implies && 1^3 + \cdots + (k-1)^3 + k^3 &< \frac{k^4}{4} + k^3 & (\text{Adding } k^3)\\ \implies && 1^3 + \cdots + k^3 &< \frac{k^4 + 4k^3}{4} \\ \implies && 1^3 + \cdots + k^3 &< \frac{k^4 + 4k^3 + 6k^2 + 4k + 1}{4} & (\text{Adding positive terms to the right})\\ \implies && 1^3 + \cdots + k^3 &< \frac{(k+1)^4}{4}. \end{align*}$

Thus, if the inequality on the left is true for $k$ then it is true for $k+1$ . Since we have shown it is true for $n =1$ , we have that it is true for all $n \in \mathbb{Z}_{>0}$ .
Now, for the inequality on the right

$\begin{align*} && \frac{k^4}{4} &< 1^3 + \cdots + k^3 \\ \implies && \frac{k^4}{4} + (k+1)^3 &< 1^3 + \cdots + (k+1)^3 & (\text{Adding } (k+1)^3) \\ \implies && \frac{k^4}{4} + k^3 + 3k^2 + 3k + 1 &< 1^3 + \cdots + (k+1)^3 \\ \implies && \frac{k^4 + 4k^3 + 12k^2 + 12k + 4}{4} &< 1^3 + \cdots + (k+1)^3 \\ \implies && \frac{k^4 + 4k^3 + 6k^2 + 4k + 1}{4} &< 1^3 + \cdots + (k+1)^3 & (\text{Making the left smaller})\\ \implies && \frac{(k+1)^4}{4} &< 1^3 + \cdots + (k+1)^3. \end{align*}$

Thus, if the inequality on the right is true for $k$ , it is also true for $k+1$ . Hence, since we have established that it is true for $n =1$ , we have that it is true for all $n \in \mathbb{Z}_{>0}. \qquad \blacksquare$