Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1970 Canadian MO Problems/Problem 9"

(Created page with "== Problem == 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 wh...")
 
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
== Problem ==
+
== Problem 9 ==
 +
Let <math>f(n)</math> be the sum of the first <math>n</math> terms of the sequence
 +
<cmath> 0, 1,1, 2,2, 3,3, 4,4, 5,5, 6,6, \ldots\, .  </cmath>
 +
a) Give a formula for <math>f(n)</math>.
  
−
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 <math>f(s+t)-f(s-t)=st</math> where <math>s</math> and <math>t</math> are positive integers and <math>s>t</math>.
−
b) Prove that f(s+t)-f(s-t)=st where s and t are positive integers and s>t.  
 
  
 
== Solution ==
 
== Solution ==
 +
 +
'''Part a):'''
 +
 +
<math>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}</math>
 +
 +
<math>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}</math>
 +
 +
<math>f(n)=\begin{cases} \frac{n^2-1}{4},\; & n\;is\;odd \\
 +
                    \frac{n^2}{4},\; & n\;is\;even\end{cases}</math>
 +
 +
Using <math>(-1)^n</math> in the formula we can have:
 +
 +
<math>\frac{(-1)^n-1}{2}=\begin{cases} -1,\; & n\;is\;odd \\
 +
                    0,\; & n\;is\;even\end{cases}</math>
 +
 +
Therefore,
 +
 +
<math>f(n)=\frac{n^2+\frac{(-1)^n-1}{2}}{4}</math>
 +
 +
<math>f(n)=\frac{2n^2-1+(-1)^n}{8}</math>
 +
 +
'''Part b):'''
 +
 +
<math>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}</math>
 +
 +
since <math>(s+t)\equiv (s-t)\;(mod\;2)</math>, then <math>(-1)^{s+t}=(-1)^{s-t}</math> and our expression reduces to:
 +
 +
<math>f(s+t)-f(s-t)=\frac{2(s+t)^2-2(s-t)^2}{8}=\frac{(s+t)^2-(s-t)^2}{4}</math>
 +
 +
<math>f(s+t)-f(s-t)=\frac{s^2+2st+t^2-s^2+2st-t^2}{4}=\frac{4st}{4}=st</math>
 +
 +
Tomas Diaz. orders@tomasdiaz.com
 +
 +
{{alternate solutions}}

Latest revision as of 23:31, 27 November 2023

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1970_Canadian_MO_Problems/Problem_9&oldid=206200"