Kvant Math Problem 1326
The recurrence can be rewritten in a much more suggestive form:
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m34s
Source on kvant.digital
Problem
The sequence $(a_n)$ is defined by the following rules: $$a_0=9,\ a_{k+1}=3a_k^4+4a_k^3, \quad\text{для любого } k \gt 0.$$ Prove that $a_{10}$ contains more than 1000 nines (in its decimal representation).
M. N. Vyalyi
Exploration
The recurrence can be rewritten in a much more suggestive form:
$$a_{k+1}=3a_k^4+4a_k^3=a_k^3(3a_k+4).$$
Since $a_0=9$, the first few terms are divisible by large powers of $9$. Let $v_9(x)$ denote the exponent of $9$ in $x$. Because
$$3a_k+4\equiv 4 \pmod 9$$
whenever $9\mid a_k$, the factor $3a_k+4$ is not divisible by $9$. Hence
$$v_9(a_{k+1})=3v_9(a_k).$$
Starting from $v_9(a_0)=1$, this gives
$$v_9(a_k)=3^k.$$
Thus
$$a_{10}=9^{3^{10}}m,$$
where $m$ is an integer not divisible by $9$.
The decimal representation of $9^n$ has a well known form modulo powers of $10$:
$$9=(10-1),\qquad 9^n=(10-1)^n.$$
Expanding binomially,
$$9^n=\sum_{j=0}^{n}(-1)^j\binom{n}{j}10^j.$$
Modulo $10^n$, all terms with $j\ge n$ disappear, so
$$9^n\equiv \sum_{j=0}^{n-1}(-1)^j\binom{n}{j}10^j \pmod{10^n}.$$
If every coefficient $\binom{n}{j}$ for $0\le j<n$ is smaller than $10$, then no carrying occurs in the decimal subtraction process and the last $n$ digits are all $9$'s. This happens only for small $n$, so that route is not sufficient.
A better idea is to study numbers congruent to $-1$ modulo a large power of $10$. If $x\equiv -1\pmod{10^N}$, then the last $N$ digits of $x$ are all $9$'s. Therefore it is enough to prove
$$a_{10}\equiv -1 \pmod{10^{1001}}.$$
The recurrence itself suggests looking at numbers of the form $-1\pmod{10^N}$. Let
$$a_k=-1+t.$$
Then
$$3a_k^4+4a_k^3 =(-1+t)^3(1+3t).$$
Multiplying,
$$(-1+t)^3(1+3t) =-1+6t^2-8t^3+3t^4.$$
The linear term vanishes. Hence if $t$ is divisible by $10^N$, then
$$a_{k+1}+1$$
is divisible by $10^{2N}$.
Since
$$a_0=9\equiv -1\pmod{10},$$
we have $a_0+1$ divisible by $10$. Each step doubles the exponent of $10$ dividing $a_k+1$. Therefore
$$10^{2^{10}}\mid (a_{10}+1).$$
Because $2^{10}=1024>1000$, the last $1024$ digits of $a_{10}$ are $9$'s. This is the key observation.
The step most likely to hide an error is the claim that the exponent of $10$ in $a_k+1$ at least doubles. That must be checked carefully from the exact polynomial identity.
Problem Understanding
We are given the sequence
$$a_0=9,\qquad a_{k+1}=3a_k^4+4a_k^3.$$
We must prove that the decimal representation of $a_{10}$ contains more than $1000$ digits equal to $9$.
This is a Type B problem, a pure proof problem.
The core difficulty is to connect the nonlinear recurrence with the decimal expansion. The crucial idea is that a number whose last $N$ digits are all $9$'s satisfies
$$x\equiv -1\pmod{10^N}.$$
Thus we seek a rapidly growing power of $10$ dividing $a_k+1$.
Proof Architecture
Lemma 1. For every $x$,
$$3x^4+4x^3+1=(x+1)^2(3x^2-2x+1).$$
This follows by direct expansion.
Lemma 2. If $10^N\mid(x+1)$, then
$$10^{2N}\mid\bigl(3x^4+4x^3+1\bigr).$$
Apply Lemma 1 and use the factor $(x+1)^2$.
Lemma 3. For every $k\ge0$,
$$10^{2^k}\mid(a_k+1).$$
Use induction, starting from $a_0+1=10$, and apply Lemma 2 at each step.
Lemma 4. If $10^N\mid(x+1)$, then the last $N$ decimal digits of $x$ are all $9$'s.
This is exactly the meaning of $x\equiv -1\pmod{10^N}$.
The hardest part is Lemma 2, because the entire argument depends on proving that the power of $10$ at least doubles at each iteration.
Solution
Define
$$f(x)=3x^4+4x^3.$$
A direct calculation gives
$$f(x)+1 =3x^4+4x^3+1 =(x+1)^2(3x^2-2x+1).$$
Indeed,
$$(x+1)^2(3x^2-2x+1) =(x^2+2x+1)(3x^2-2x+1) =3x^4+4x^3+1.$$
Suppose $10^N\mid(x+1)$. Then $(x+1)^2$ is divisible by $10^{2N}$. From the factorization above,
$$f(x)+1=(x+1)^2(3x^2-2x+1),$$
hence
$$10^{2N}\mid(f(x)+1).$$
We now prove by induction that
$$10^{2^k}\mid(a_k+1)$$
for every $k\ge0$.
For $k=0$,
$$a_0+1=9+1=10,$$
so $10^{2^0}=10$ divides $a_0+1$.
Assume that for some $k\ge0$,
$$10^{2^k}\mid(a_k+1).$$
Applying the previous result with $x=a_k$, we obtain
$$10^{2^{k+1}} =10^{2\cdot 2^k} \mid \bigl(f(a_k)+1\bigr).$$
Since $f(a_k)=a_{k+1}$,
$$10^{2^{k+1}}\mid(a_{k+1}+1).$$
The induction is complete.
Taking $k=10$, we get
$$10^{2^{10}}\mid(a_{10}+1).$$
Since
$$2^{10}=1024,$$
it follows that
$$a_{10}\equiv -1\pmod{10^{1024}}.$$
A number congruent to $-1$ modulo $10^{1024}$ ends with $1024$ consecutive digits $9$. Therefore the decimal representation of $a_{10}$ contains at least $1024$ nines.
Because
$$1024>1000,$$
$a_{10}$ contains more than $1000$ nines.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the factorization
$$3x^4+4x^3+1=(x+1)^2(3x^2-2x+1).$$
Expanding the right-hand side,
$$(x^2+2x+1)(3x^2-2x+1) =3x^4+4x^3+(3-4+1)x^2+(2-2)x+1,$$
which simplifies to
$$3x^4+4x^3+1.$$
No terms remain in degrees $2$ or $1$.
The second delicate step is the doubling of the power of $10$. From
$$10^N\mid(x+1),$$
we obtain
$$10^{2N}\mid(x+1)^2.$$
The factor $3x^2-2x+1$ need not be divisible by $10$, but this is irrelevant because divisibility by $10^{2N}$ already comes from $(x+1)^2$. Thus the exponent cannot decrease.
The third delicate step is translating congruence into decimal digits. If
$$10^N\mid(x+1),$$
then
$$x=-1+m10^N=(m-1)10^N+(10^N-1).$$
Since
$$10^N-1=99\ldots9$$
with $N$ digits, the last $N$ digits of $x$ are all $9$'s. Applying this with $N=1024$ yields $1024$ trailing nines.
Alternative Approaches
Instead of factoring $3x^4+4x^3+1$, one may write $x=-1+t$. Substituting into the recurrence gives
$$a_{k+1} =-1+6t^2-8t^3+3t^4.$$
Hence
$$a_{k+1}+1=t^2(6-8t+3t^2).$$
If $t$ is divisible by $10^N$, then $a_{k+1}+1$ is divisible by $10^{2N}$. This yields the same doubling phenomenon directly.
The factorization method is preferable because it isolates the essential algebraic structure in a single identity and makes the inductive step immediate.