Putnam 1999 A6

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Putnam 1999 A6

G H J

Reveal topic tags

college contests

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7938 posts

#1 h Dec 22, 2012, 6:57 PM • 2 Y

Y by Adventure10, Mango247

The sequence $(a_n)_{n\geq 1}$ is defined by $a_1=1,a_2=2,a_3=24,$ and, for $n\geq 4,$ $a_n=\dfrac{6a_{n-1}^2a_{n-3}-8a_{n-1}a_{n-2}^2}{a_{n-2}a_{n-3}}.$ Show that, for all $n$ , $a_n$ is an integer multiple of $n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7938 posts

#2 h Dec 22, 2012, 6:58 PM • 2 Y

Y by Adventure10, Mango247

Note: I am aware that this is a PEN problem as well. However, the wording is slightly different, and I wanted to keep the wordings in the Contests page true to form.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2903 posts

#3 h Dec 22, 2012, 8:46 PM • 2 Y

Y by Adventure10, Mango247

Define $b_n = a_n/a_{n-1}$ . After a bit of algebra note that $b_n = 6b_{n-1} - 8b_{n-2}$ . By solving the recurrence relation one easily finds $b_{n+1} = 4^n - 2^n$ . Thus it follows $a_n = \prod_{i=1}^{n-1} (4^i - 2^i) = 2^{i(i-1)/2} \prod_{i=1}^{n-1} (2^i - 1)$ and then finishing here is easy with LTE, just show $n!|2^{i(i-1)/2} \prod_{i=1}^{n-1} (2^i - 1)$ using an identical argument to http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=495621&p=2783008

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

307 posts

#4 h Apr 15, 2025, 1:38 PM

Y by

For all integers $n\geq 2,$ define $b_n=\dfrac{a_n}{a_{n-1}}.$ Note that $b_n=\dfrac{a_n}{a_{n-1}}=\dfrac{6a_{n-1}a_{n-3}-8a_{n-2}^2}{a_{n-2}a_{n-3}}=\dfrac{6a_{n-1}}{a_{n-2}}-\dfrac{8a_{n-2}}{a_{n-3}}=6b_{n-1}-8b_{n-2}$ for all positive integers $n\geq 4.$ Then, $b_n-2b_{n-1}=4b_{n-1}-8b_{n-2}=4(b_{n-1}-2b_{n-2})$ for all integers $n\geq 4,$ so if we let $c_n=b_n-2b_{n-1}$ for all integers $n\geq 3,$ we have $c_n=4c_{n-1}$ for all integers $n\geq 4.$

Note that $c_3=b_3-2b_2=\dfrac{a_3}{a_2}-\dfrac{2a_2}{a_1}=12-4=8=2^{2\cdot 3-3},$ so for all integers $n\geq 3,$ $c_n=2^{2n-3}.$

We now claim that, for all integers $n \geq 2,$ that $b_n=2^{n-1}(2^{n-1}-1).$ We proceed with induction.

Note that $b_2=2=2^{2-1}(2^{2-1}-1),$ so the base case holds. Now, assume there exists an integer $k\geq 3$ such that $a_{k-1}=2^{k-2}(2^{k-2}-1).$ Then, $2^{2k-3}=c_k=b_k-2b_{k-1}=b_k-2(2^{k-2})(2^{k-2}-1)=b_k-2^{k-1}(2^{k-2}-1),$ so $b_k=2^{k-1}(2^{k-2}-1)+2^{2k-3}=2^{k-1}(2^{k-2}+2^{k-2}-1)=2^{k-1}(2\cdot 2^{k-2}-1)=2^{k-1}(2^{k-1}-1),$ so by the principle of mathematical induction, $b_n=2^{n-1}(2^{n-1}-1)$ for all integers $n\geq 2.$

Now, for all integers $n\geq 2,$ $a_n=a_1\displaystyle\prod_{i=2}^{n} \dfrac{a_i}{a_{i-1}}=\displaystyle\prod_{i=2}^{n} b_i=\displaystyle\prod_{i=2}^{n} 2^{i-1}(2^{i-1}-1)=\displaystyle\prod_{i=1}^{n-1} 2^i(2^i-1).$

For all positive integers $n,$ denote $f(n)$ to be the largest integer power of $2$ that divides $n,$ and denote $g(n)$ to be the largest odd integer that divides $n.$ It suffices to prove that $f(n)\mid a_n$ and $g(n)\mid a_n$ for all positive integers $n.$

We first prove $f(n)\mid a_n$ for all positive integers $n.$

Lemma: For all integers $n\geq 1,$ we have $n<2^n.$

Proof:

We proceed with induction on $n.$ Clearly, $1<2^1,$ so the base case holds. Now, assume there exists an integer $k\geq 1$ such that $k<2^k.$ Then, $2^{k+1}=2\cdot 2^k>2k\geq k+1,$ so by the principle of mathematical induction, $n<2^n$ for all positive integers $n,$ as desired.

Now, note that $f(n)\leq n < 2^n,$ so there exists an integer $1\leq i \leq n-1$ such that $2^i=f(n),$ and thus $f(n)\mid \displaystyle\prod_{i=1}^{n-1} 2^i(2^i-1)=a_n.$ for all integers $n\geq 2,$ and $f(1)=1\mid a_1,$ so $f(n)\mid a_n$ for all positive integers $n.$

We now prove $g(n)\mid a_n$ for all positive integers $n.$

Since $\gcd(2,g(n))=1$ for all positive integers $n,$ by Euler's theorem, $2^{\phi(g(n))}-1\equiv 0\pmod{g(n)}.$

Observe that if $g(n)=1,$ then obviously $g(n)\mid a_n.$ If $g(n)\neq 1,$ then $\phi(g(n))<g(n)\leq n,$ so $\phi(g(n))\leq n-1.$ Thus, $g(n)\mid 2^{\phi(g(n))}-1\mid \displaystyle\prod_{i=1}^{n-1} 2^i(2^i-1).$ Thus, $g(n)\mid a_n$ for all positive integers $n.$

Now, since $f(n)\mid a_n$ and $g(n)\mid a_n$ for all positive integers $n,$ we have $n\mid a_n$ for all positive integers $n,$ as desired. $\Box$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a