Tag: Sums

Compute some integrals of step functions

by RoRi

July 18, 2015

Let $n \in \mathbb{Z}_{>0}$ , prove
$\int_0^n [t] \, dt = \frac{n(n-1)}{2}.$
Let $x \in \mathbb{R}_{>0}$ , and define
$f(x) = \int_0^x [t] \, dt.$

Draw the graph of $f$ for $0 \leq x \leq 4$ .

Proof. Let $P = \{ 0,1,2, \ldots, n \}$ be a partition of $[0,n]$ . Then, by the definition of the greatest integer function, $[t]$ is constant on the open subintervals of $P$ , so
$\begin{align*} \int_0^n [t] \, dt &= \sum_{k=1}^n (k-1)(k-(k-1)) & (s_k = k-1 \text{ since } [t]=k-1 \text{ if } k-1 < t < k)\\ &= \sum_{k=1}^n (k-1) \\ &= \sum_{k=0}^{n-1} k \\ &= \frac{n(n-1)}{2}. \end{align*}$

The final equality follows from here (I.4.7, #5) $. \qquad \blacksquare$
The graph is:

Prove a formula for the sum of [(na)/b] where a,b are relatively prime integers

by RoRi

July 17, 2015

Let $a,b$ be relatively prime positive integers (i.e., they have no common factors other than 1). Then we have the formula

$\sum_{n=1}^{b-a} \left[ \frac{na}{b} \right] = \frac{(a-1)(b-1)}{2}.$

The sum is 0 when $b=1$ .

Prove this result by a geometric argument.
Prove this result by an analytic argument.

Proof. We know by the previous exercise (1.11, #6) that
$\sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] = \begin{array}{l} \text{\# of lattice points inside a right triangle}\\ \text{of base } b \text{ and height } a \ (\text{letting } f(x) = \frac{ax}{b}).\end{array}$

Further, from this exercise (1.7, #4), we know

$a(T) = I_T + \frac{1}{2} B_T - 1$

where $I_T =$ number of interior lattice points, and $B_T =$ number of boundary lattice points. We also know by the formula for the area of a right triangle that

$a(T) = \frac{1}{2} (ab).$

Thus, we have,

$I = \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] = \frac{1}{2} (ab) - \frac{1}{2}B_T + 1.$

Then, to calculate $B_T$ we note there are no boundary points on the hypotenuse of our right triangle (since $a$ and $b$ have no common factor). (This follows since if there were such a point then $\frac{na}{b} \in \mathbb{Z}$ for some $n < b$ , but then we would have $a$ divides $b$ , contradicting that they have no common factor.) Thus, $B_T = a + b + 1$ . So,

$\begin{align*} \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] &= \frac{1}{2} (ab) - \frac{1}{2} (a+b+1) +1 \\ &= \frac{1}{2} (ab - a - b + 1) \\ &= \frac{1}{2} (a-1)(b-1). \qquad \blacksquare \end{align*}$
Proof. To derive the result analytically, first, by counting in the other direction we have,
$\sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] = \sum_{n=1}^{b-1} \left[ \frac{a(b-n)}{b} \right].$

Then,

$\begin{align*} && \sum_{n=1}^{b-1} \left[ \frac{a(b-n)}{b} \right] &= \sum_{n=1}^{b-1} [a] - \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] - \sum_{n=1}^{b-1} 1 \\ \implies && 2 \sum_{n=1}^{b-1} \left[ \frac{a(b-n)}{b} \right] &= \sum_{n=1}^{b-1} [a] - \sum_{n=1}^{b-1} 1 = (b-1)a - (b-1)\\ \implies && \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] &= \frac{1}{2} (a-1)(b-1). \qquad \blacksquare \end{align*}$

Find a formula for a sum of 1/k(k+1)

by RoRi

July 6, 2015

Claim:

$\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$

Proof. The proof is by induction. If $n = 1$ then on the left we have

$\sum_{k=1}^n \frac{1}{k(k+1)} = \sum_{k=1}^1 \frac{1}{k(k+1)} = \frac{1}{2}.$

On the right,

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

So, indeed, the formula holds for the case $n=1$ .
Assume then that the formula is true for some $n=m \in \mathbb{Z}_{\geq 1}$ . Then,

$\begin{align*} &&\sum_{k=1}^m \frac{1}{k(k+1)} &= 1 - \frac{1}{m+1} \\ \implies && \left(\sum_{k=1}^{m} \frac{1}{k(k+1)}\right) + \frac{1}{(m+1)(m+2)} &= 1 - \frac{1}{m+1} + \frac{1}{(m+1)(m+2)} \\ \implies && \sum_{k=1}^{m+1} \frac{1}{k(k+1)} &= 1 - \frac{m+2-1}{(m+1)(m+2)}\\ \implies && \sum_{k=1}^{m+1} \frac{1}{k(k+1)} &= 1 - \frac{1}{m+2} \end{align*}$

Thus, the formula holds for $m+1$ ; and thus, for all $n \in \mathbb{Z}_{\geq 1}. \qquad \blacksquare$

Evaluate if some formulas for finite sums are true or false

by RoRi

July 6, 2015

$\displaystyle{\sum_{n=0}^{100} n^4 = \sum_{n=1}^{100} n^4}.$
$\displaystyle{\sum_{j=0}^{100} 2 = 200}.$
$\displaystyle{\sum_{k=0}^{200} (2+k) = 2 + \sum_{k=0}^{100} k}.$
$\displaystyle{\sum_{i=1}^{100} (i+1)^2 = \sum_{i=0}^{99} i^2}.$
$\displaystyle{\sum_{k=1}^{100} k^3 = \left(\sum_{k=1}^{100} k \right) \left( \sum_{k=1}^{100} k^2 \right)}.$
$\displaystyle{\sum_{k=0}^{100} k^3} = \left( \sum_{k=0}^{100} \right)^3}.$

True. Since $0^4 = 0$ the extra term on the left has no impact on the sum. In other words,

$\sum_{n=0}^{100} n^4 = 0^4 + \sum_{n=1}^{100} n^4 = \sum_{n=1}^{100} n^4.$
False. We know from here that $\sum_{j=1}^{100} 1 = 100$ ; hence,

$\sum_{j=0}^{100} 2 = 2 \left(1 + \sum_{j=1}^{100} 1 \right) = 202.$

(The “problem” here is the extra term in the sum. The $j=0$ term actually contributes to the sum since 2 evaluated at $j=0$ is still 2.)
False. This is just abusing the additive property of finite sums. In reality,

$\sum_{k=0}^{200} (2+k) = \left( \sum_{k=0}^{200} 2 \right) + \left( \sum_{k=0}^{200} k \right) = 202 + \sum_{k=0}^{100} k.$
False. This is reindexing the sum incorrectly. Seeing, $(i+1)^2$ the idea is to replace a sum over $i$ , by a sum over $i+1$ to get a simpler expression. (A quick and dirty way to see that this has not been reindexed correctly is by looking at the first few terms. The sum on the left starts $2^2 + 3^2 + 4^2 + \cdots$ , while the sum on the right starts $0^2 + 1^2 + 2^2 + \cdots$ . To do this correctly, we replace $i+1$ by $i$ in the interior, and then have to add one to the top and bottom indices so that we have $i+1=2$ to 101 and can replace the $i+1$ by $i$ . This is the way I think about it; there are probably better ways.) Anyway, reindexing properly we would get,

$\sum_{i=1}^{100} (i+1)^2 = \sum_{i=2}^{101} i^2.$

Or we could actually expand out the $(i+1)^2$ squared term and use linearity to separate the sums and evaluate all of them separately, but that would be slower.
False. Sums and powers just don’t work this way. (This is really claiming $(1^3 + 2^3 + \cdots + 100^3) = (1+2 + \cdots +100)(1^2 + 2^2 + \cdots + 100^2)$ .) From work we did earlier (see: sums of integers, sums of squares, and sums of cubes) we have,

$\sum_{k=1}^n k^3 = \frac{n^4}{4} + \frac{n^3}{2} + \frac{n^2}{4},$

while

$\left( \sum_{k=1}^n k \right) \left( \sum_{k=1}^n k^2 \right) = \left( \frac{n^2}{2} + \frac{n}{2} \right) \left( \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6} \right).$

One can then plug in $n=100$ to see that we get 25502500 on the left, but 1708667500 on the right.
False. Again, this just wrong. The claim is that $(1^3 + 2^3 + \cdots + 100^3) = (1 + 2 + \cdots + 100)^3$ , which is of course false. More concretely, we know

$\sum_{k=0}^{n} k^3 = \frac{n^4}{4} + \frac{n^3}{2} + \frac{n^2}{4},$

while

$\left( \sum_{k=0}^n k \right)^3 = \left( \frac{n^2}{2} + \frac{n}{2} \right)^3.$

So, evaluating at $n=100$ , we have 25502500 on the right and 128787625000 on the right.

Formula for sum of the reciprocals of integers

by RoRi

July 6, 2015

Give a definition of $\sum_{k=m}^{m+n} a_k$ .
Prove the following is true for $n \geq 1$ :
$\sum_{k=n+1}^{2n} \frac{1}{k} = \sum_{m=1}^{2n} \frac{(-1)^{m+1}}{m}.$

We define
$\sum_{k=m}^{m+n} a_k = a_m + a_{m+1} + \cdots + a_{m+n}.$
Proof. The proof is by induction. For the case $n = 1$ we have, on the left,

$\sum_{k=n+1}^{2n} \frac{1}{k} = \sum_{k=2}^2 \frac{1}{k} = \frac{1}{2}.$

On the right,

$\sum_{m=1}^{2n} \frac{(-1)^{m+1}}{m} = \sum_{m=1}^2 \frac{(-1)^{m+1}}{m} = 1 - \frac{1}{2} = \frac{1}{2}.$

Thus, the formula holds for the case $n = 1$ . Assume then that it holds for some $n = j \in \mathbb{Z}_{\geq 1}$ . Then we have,

$\begin{align*} &&\sum_{k=j+1}^{2j} \frac{1}{k} &= \sum_{m=1}^{2j} \frac{(-1)^{m+1}}{m} \\ \implies && \left(\sum_{k=j+1}^{2j} \frac{1}{k}\right) + \frac{1}{2j+1} + \frac{1}{2j+2} &= \left(\sum_{m=1}^{2j} \frac{(-1)^{m+1}}{m}\right) + \frac{1}{2j+1} + \frac{1}{2j+2} \\ \implies && \sum_{k=j+1}^{2(j+1)} \frac{1}{k} &= \left(\sum_{m=1}^{2j} \frac{(-1)^{m+1}}{m}\right) + \frac{1}{2j+1} + \frac{1}{2j+2} \\ \implies && \frac{1}{j+1} + \left(\sum_{k=j+2}^{2(j+1)} \frac{1}{k} \right)&= \left(\sum_{m=1}^{2j} \frac{(-1)^{m+1}}{m}\right) + \frac{1}{2j+1} + \frac{1}{2j+2} \\ \implies && \sum_{k=j+2}^{2(j+1)} \frac{1}{k} &= \left( \sum_{m=1}^{2j} \frac{(-1)^{m+1}}{m} \right) + \frac{1}{2j+1} + \frac{1}{2(j+1)} - \frac{1}{j+1} \\ \implies && \sum_{k=j+2}^{2(j+1)} \frac{1}{k} &= \left( \sum_{m=1}^{2j} \frac{(-1)^{m+1}}{m} \right) + \frac{1}{2j+1} - \frac{1}{2(j+1)} \\ \implies && \sum_{k=j+2}^{2(j+1)} \frac{1}{k} &= \sum_{m=1}^{2(j+1)} \frac{(-1)^{m+1}}{m}. \end{align*}$

Thus, the formula holds for $j+1$ if it holds for $j$ ; hence, we have shown that it holds for all $n \in \mathbb{Z}_{\geq 1}. \qquad \blacksquare$

Prove by induction a property of the alternating sum of odd integers

by RoRi

July 6, 2015

Prove that

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

This implies the sum is proportional to $n$ with constant of proportionality 2.

Proof. The proof is by induction. For the case $n = 1$ we have, on the left,

$\sum_{k=1}^{2n} (-1)^k (2k+1) = \sum_{k=1}^2 (-1)^k (2k+1) = -3 + 5 = 2.$

On the right we have $2n = 2$ . Hence, the formula holds for this case.
Assume then that the formula holds for some $n = m \in \mathbb{Z}_{>0}$ . Then,

$\begin{alignat*}{2} \sum_{k=1}^{2m} (-1)^k (2k+1) = 2m \qquad &\implies & \sum_{k=0}^{2(m+1)} (-1)^k (2k+1) &= 2m - (2(2m+1)+1) + (2(2m+2)+1) \\ &&&= 2m - 4m - 3 + 4m + 5 \\ &&&= 2(m+1). \end{alignat*}\end{align*}$

Thus, if the statement is true for $m$ then it is true for $m+1$ . Hence, we have established the statement is true for all $n \in \mathbb{Z}_{>0}. \qquad \blacksquare$

Sum of the k-th powers of x for k = 0 to n

by RoRi

July 5, 2015

Prove that
$\sum_{k=0}^n x^k = \frac{1-x^{n+1}}{1-x} \qquad \text{for } x \neq 1.$

Proof. We use properties of finite sums to compute,

$(1-x) \sum_{k=0}^n x^k = \sum_{k=0}^n (x^k - x^{k+1}) = - \sum_{k=0}^n (x^{k+1} -x^k) = -(x^{n+1} - 1) = 1-x^{n+1}.$

The second to last inequality follows from the telescoping property. But then solving for the sum we are interested in, we have

$\sum_{k=0}^n x^k = \frac{1-x^{n+1}}{1-x}. \qquad \blacksquare$
If $x = 1$ we have (using this, and the fact that $1^k = 1$ for $k = 0, \ldots, n$ )
$\sum_{k=0}^n x^k = \sum_{k=0}^n 1 = n+1.$

Formula for the sum of the cubes from 1 to n

by RoRi

July 5, 2015

Prove that

$\sum_{k=1}^n k^3 = \frac{n^4}{4} + \frac{n^3}{2} + \frac{n^2}{4}.$

Proof. We follow a similar strategy to this one. From here, here, and here we have

$\sum_{k=1}^n 1 = n, \qquad \sum_{k=1}^n k = \frac{n^2}{2} + \frac{n}{2}, \qquad \sum_{k=1}^n k^2 = \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}.$

Then, since $k^4 - (k-1)^4 = 4k^3 - 6k^2 + 4k -1$ and by the telescoping property $\sum_{k=1}^n (k^4 - (k-1)^4) = n^4$ , we have,

$\begin{align*} n^4 &= \sum_{k=1}^n (4k^3 - 6k^2 + 4k - 1) \\ &= 4 \sum_{k=1}^n k^3 - 6 \sum_{k=1}^n k^2 + 4 \sum_{k=1}^n k - \sum_{k=1}^n 1 \\ \implies \sum_{k=1}^n k^3 &= \frac{1}{4} \left( n^4 + 6 \sum_{k=1}^n k^2 - 4 \sum_{k=1}^n k + \sum_{k=1}^n 1\right) \\ &= \frac{n^4}{4} + \frac{3}{2}\left(\frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6} \right) - \left( \frac{n^2}{2} + \frac{n}{2} \right) + \frac{n}{4} \\ &= \frac{n^4}{4} + \frac{n^3}{2} + \frac{n^2}{4}. \qquad \blacksquare \end{align*}$

Formula for the sum of squares from 1 to n

by RoRi

July 5, 2015

Prove that

$\sum_{k=1}^n n^2 = \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}.$

Proof. We know $k^3 - (k-1)^3 = 3k^2 - 3k + 1$ , and the from the telescoping property we have,

$\sum_{k=1}^n (k^3 - (k-1)^3) = n^3.$

So, using the additivity and homogeneity properties of finite sums, we have,

$\begin{align*} n^3 = \sum_{k=1}^n (3k^2 - 3k + 1) & \implies n^3 = 3\sum_{k=1}^n k^2 - 3 \sum_{k=1}^n k + \sum_{k=1}^n 1 \\ & \implies \sum_{k=1}^n k^2 = \frac{n^3}{3} + \sum_{k=1}^n k - \frac{1}{3} \sum_{k=1}^n 1 \end{align*}$

But, we know that $\sum_{k=1}^n k = \frac{n^2}{2} + \frac{n}{2}$ and we know $\sum_{k=1}^n 1 = n$ . So,

$\begin{align*} \sum_{k=1}^n k^2 &= \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{2} - \frac{n}{3} \\ &= \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}. \qquad \blacksquare \end{align*}$

Formula for the sum of the first n integers

by RoRi

July 5, 2015

Prove that

$\sum_{k=1}^n k = \frac{n^2}{2} + \frac{n}{2}.$

Proof. From here we know that

$\sum_{k=1}^n 1 = n$

and from here, that

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

By additivity and homogeneity of finite sums we have,

$\sum_{k=1}^n (2k-1) = 2 \sum_{k=1}^n k - \sum_{k=1}^n 1 = n^2 \quad \implies \quad \sum_{k=1}^n k = \frac{n^2}{2} + \frac{n}{2}. \qquad \blacksquare$