1970 Canadian MO Problems/Problem 9

Problem 9

Let $f(n)$ be the sum of the first $n$ terms of the sequence $0, 1,1, 2,2, 3,3, 4,4, 5,5, 6,6, \ldots\, .$ a) Give a formula for $f(n)$ .

b) Prove that $f(s+t)-f(s-t)=st$ where $s$ and $t$ are positive integers and $s>t$ .

Solution

Part a):

$f(n)=\begin{cases} 2\sum_{k=1}^{\frac{n-1}{2}}k,\; & n\;is\;odd \\ 2\sum_{k=1}^{\frac{n}{2}}k-\frac{n}{2},\; & n\;is\;even\end{cases}$

$f(n)=\begin{cases} \left( \frac{n-1}{2} \right)\left( \frac{n-1}{2}+1 \right),\; & n\;is\;odd \\ \left( \frac{n}{2} \right)\left( \frac{n}{2}+1 \right)-\frac{n}{2},\; & n\;is\;even\end{cases}$

$f(n)=\begin{cases} \frac{n^2-1}{4},\; & n\;is\;odd \\ \frac{n^2}{4},\; & n\;is\;even\end{cases}$

Using $(-1)^n$ in the formula we can have:

$\frac{(-1)^n-1}{2}=\begin{cases} -1,\; & n\;is\;odd \\ 0,\; & n\;is\;even\end{cases}$

Therefore,

$f(n)=\frac{n^2+\frac{(-1)^n-1}{2}}{4}$

$f(n)=\frac{2n^2-1+(-1)^n}{8}$

Part b):

$f(s+t)-f(s-t)=\frac{2(s+t)^2-1+(-1)^{s+t}}{8}-\frac{2(s-t)^2-1+(-1)^{s-t}}{8}$

since $(s+t)\equiv (s-t)\;(mod\;2)$ , then $(-1)^{s+t}=(-1)^{s-t}$ and our expression reduces to:

$f(s+t)-f(s-t)=\frac{2(s+t)^2-2(s-t)^2}{8}=\frac{(s+t)^2-(s-t)^2}{4}$

$f(s+t)-f(s-t)=\frac{s^2+2st+t^2-s^2+2st-t^2}{4}=\frac{4st}{4}=st$

Tomas Diaz. orders@tomasdiaz.com

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Page

Toolbox

Search

1970 Canadian MO Problems/Problem 9

Problem 9

Solution