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 "1974 IMO Problems/Problem 3"

(Created page with "==Problem== Prove that the number <math>\sum^n_{k=0}\binom{2n+1}{2k+1}2^{3k}</math> is not divisible by <math>5</math> for any integer <math>n\ge0.</math> ==Solution== {{solu...")
 
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
Everything that follows takes place in <math>\mathbb F_5(\sqrt 2)</math>, i.e. the field we get by adjoining a root of <math>x^2-2=0</math> to <math>\mathbb F_5</math>, the field with <math>5</math> elements.
 +
 
 +
We have <math>\sum_{k=0}^n\binom{2n+1}{2k+1}2^{3k}=\sum_{k=0}^n\binom{2n+1}{2n-2k}3^k=\sum_{k=0}^n\binom{2n+1}{2(n-k)}2^{-k}</math>. Now, this is zero iff it's zero when we multiply it by <math>2^n</math>, so we may as well prove that <math>\sum_{k=0}^n\binom{2n+1}{2(n-k)}\sqrt 2^{2(n-k)}\ne 0</math>. The LHS is <math>\alpha</math> from <math>(1+\sqrt 2)^{2n+1}=\alpha+\beta\sqrt 2,\ \alpha,\beta\in\mathbb F_5</math>. We have <math>(1-\sqrt 2)^{2n+1}=\alpha-\beta\sqrt 2</math>, so by multiplying them we get <math>-1=\alpha^2-2\beta^2</math>. If we were to have <math>\alpha=0</math>, then we would get <math>1=2\beta^2,\ \beta\in\mathbb F_5</math>, and this is impossible, since it would make <math>3=2^{-1}</math> a square <math>\beta^2</math> in <math>\mathbb F_5</math> (i.e. <math>3</math> would be a quadratic residue modulo <math>5</math>, and it's not).
 +
 
 +
The above solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [https://aops.com/community/p359102]
 +
 
 +
{{alternate solutions}}
  
 
==See Also==
 
==See Also==

Revision as of 14:58, 29 January 2021

Problem

Prove that the number $\sum^n_{k=0}\binom{2n+1}{2k+1}2^{3k}$ is not divisible by $5$ for any integer $n\ge0.$

Solution

Everything that follows takes place in $\mathbb F_5(\sqrt 2)$, i.e. the field we get by adjoining a root of $x^2-2=0$ to $\mathbb F_5$, the field with $5$ elements.

We have $\sum_{k=0}^n\binom{2n+1}{2k+1}2^{3k}=\sum_{k=0}^n\binom{2n+1}{2n-2k}3^k=\sum_{k=0}^n\binom{2n+1}{2(n-k)}2^{-k}$. Now, this is zero iff it's zero when we multiply it by $2^n$, so we may as well prove that $\sum_{k=0}^n\binom{2n+1}{2(n-k)}\sqrt 2^{2(n-k)}\ne 0$. The LHS is $\alpha$ from $(1+\sqrt 2)^{2n+1}=\alpha+\beta\sqrt 2,\ \alpha,\beta\in\mathbb F_5$. We have $(1-\sqrt 2)^{2n+1}=\alpha-\beta\sqrt 2$, so by multiplying them we get $-1=\alpha^2-2\beta^2$. If we were to have $\alpha=0$, then we would get $1=2\beta^2,\ \beta\in\mathbb F_5$, and this is impossible, since it would make $3=2^{-1}$ a square $\beta^2$ in $\mathbb F_5$ (i.e. $3$ would be a quadratic residue modulo $5$, and it's not).

The above solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [1]

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

See Also

1974 IMO (Problems) • Resources
Preceded by
Problem 2 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 4
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1974_IMO_Problems/Problem_3&oldid=143898"