The equation $x^3-3x^2+1=0$ has three real solutions $x_1<x_2<x_3$. Show that for any positive integer $n$, the number $\left\lceil x_3^n\right\rceil$ is a multiple of $3$.
Problem
Source: Germany 2023, Problem 6
Tags: algebra, number theory proposed, algebra proposed, ceiling function, cubic equation
WallyWalrus
16.06.2023 20:26
Denote $P(x)=x^3-3x^2+1$. $P(-1)<0,\,P(0)>0,\;P(1)<0\Longrightarrow x_1\in(-1,0);\;x_2\in(0,1)$. $P(2)<0,\,P(3)>0\Longrightarrow x_3\in(2,3)$. A more precise calculus gives us: $x_1\in\left(-\dfrac{6}{10},-\dfrac{5}{10}\right);\;x_2\in\left(\dfrac{6}{10},\dfrac{7}{10}\right)$. Results: $|x_2|>|x_1|\Longrightarrow x_1^n+x_2^n>0,\;\forall n\in\mathbb{N}$; $x_1^n+x_2^n\le|x_1^n|+|x_2^n|\le|x_1^2|+|x_2^2|<\dfrac{36}{100}+\dfrac{49}{100}<1,\;\forall n\ge2$, hence $0<x_1^n+x_2^n<1,\;\forall n\ge2$. For $n=1:\;x_1\in(2,3)\Longrightarrow \lceil x_3\rceil=3\Longrightarrow 3|\lceil x_3\rceil$. For $n=2$: Using the Vieta's relations: $x_1+x_2+x_3=3;\;x_1x_2+x_2x_3+x_3x_1=0\Longrightarrow$ $\Longrightarrow x_1^2+x_2^2+x_3^2=(x_1+x_2+x_3)^2-2(x_1x_2+x_2x_3+x_3x_1)=9\Longrightarrow$ $\Longrightarrow x_3^2=9-(x_1^2+x_2^2)\in(8,9)\Longrightarrow \lceil x_3\rceil=9\Longrightarrow 3|\lceil x_3\rceil$. For $n\ge3$: Denote $S_k=x_1^k+x_2^k+x_3^k$. We prove by induction: $S_k>S_{k-1};\;S_k\in\mathbb{N}$ and $3|S_k,\;\forall k\in\mathbb{N},\; k\ge3$. The initial step: $S_1=3;\;S_2=9$. $P(x_1)=0\Longrightarrow x_1^3=3x_1^2-1$ and similar for $x_2,x_3\Longrightarrow S_3=3S_2-3=24>S_2>S_1;\;3|S_3$. The induction step: let be $k\ge3$. Assume $S_{k-2},S_{k-1},S_k\in\mathbb{N}$ and $S_{k-2}<S_{k-1}<S_k$ and $3|S_{k-2};\;3|S_{k-1};\;3|S_{k}$. $P(x_1)=0\Longrightarrow x_1^3=3x_1^2-1$ and similar for $x_2,x_3\Longrightarrow$ $\Longrightarrow x_1^{k+1}=3x_1^k-x_1^{k-2}$ and similar for $x_2,x_3\Longrightarrow$ $\Longrightarrow S_{k+1}=3S_k-S_{k-2}>2S_k>S_k;\;S_{k+1}=3S_k-S_{k-2}\in\mathbb{N}$ and $3|S_{k+1}$. Denote $S_n=x_1^n+x_2^n+x_3^n=3M_n$, with $M_n\in\mathbb{N}$. Results: $x_3^n=3M_n-(x_1^n+x_2^n)\in(3M_n-1,3M_n)$, since $0<x_1^n+x_2^n<1$. Results: $\lceil x_3^n\rceil=3M_n$, hence $3|\lceil x_3^n\rceil$.
bora_olmez
16.06.2023 20:36
Solved with L567, starchan, Siddharth03. The idea is quite clear so this may be a little easy for a 3/6 but oh well. The underlying intuition is that $F_n = \lceil \frac{\varphi^n}{\sqrt{5}} \rceil$ where $F_n$ is the Fibonacci sequence.
Before beginning, we plug in certain values to find:
$$P(-1) = -3 < 0, P(0) = 1 > 0, P(1) = -1 < 0, P(2) = -3, P(2\sqrt{2}) = 8\sqrt{2}-13<0, P(3) = 1 > 0$$where $\sqrt{2}<\frac{13}{8}$ as $169 > 2 \cdot 64$
The key idea is the following, presented linearly it may not make sense for somebody who has never seen the idea. Define $a_n = x_1^n+x_2^n+x_3^n$. $\textbf{Lemma 1: Recursion}$ $a_{n+3}-3a_{n+2}+a_n = 0$ for all $n \in \mathbb{Z}_{\geq 0}$
This is of course a special case of a much more general lemma and is indeed the underlying intuition for constructing this sequence ($a_n$) as such.
I will state and prove the lemma for the sake of completeness:
$\textbf{Converse of a Known Lemma:}$
Let $P(x) = a_k(x-\alpha_1)(x-\alpha_2) \cdots (x-\alpha_k) = \sum_{i=0}^{k} a_ix^i$, Then, for any $c_1, \cdots, c_k \in \mathbb{R}$, the sequence defined as $L_n = \sum_{i=1}^{k} c_i(\alpha_i)^n$ satisfies the recursion $$a_kL_{t+k}+a_{k-1}L_{t+k-1}+\cdots+a_1L_{t+1}+a_0L_t = 0$$$\textbf{Proof}$
This is simply a matter of switching the order of summation, the converse of this lemma is usually what really holds a lot of power.
Notice that $$ \sum_{i=0}^{k} a_iL_{t+i} = \sum_{i=0}^{k} a_i \sum_{j=1}^{k} c_j(\alpha_j)^{t+i} = \sum_{j=1}^{k} c_j(\alpha_j)^t \left[\sum_{i=0}^{k}a_i(\alpha_j)^i\right] = \sum_{j=1}^{j} c_j(\alpha_j)^t \cdot P(\alpha_j) = 0$$as $P(\alpha_j)=0$ for all $j \in \{1, \cdots, k\}$.
This proves the lemma. $\blacksquare$ $\blacksquare$
Now, taking $x_1 = \alpha_1, x_2 = \alpha_2, x_3 = \alpha_3, c_1 = c_2 = c_3 = 1$ immediately implies $\textbf{Lemma 1}$ as $x_1, x_2, x_3$ are precisely the three roots of monic polynomial $P(X) = X^3-3X^2+1$. $\blacksquare$
Now, we work with this recursion.
One may ask why the coefficients were chosen to be $c_1 = c_2 = c_3 = 1$, well, the fact that $c_1=1$ is clear because we wish for $a_n = \lceil x_3^n \rceil$ and then $c_2 = c_1 =1$ just seemed appropriate.
We have the following two lemmas to finish. $\textbf{Lemma 2: Mod 3}$ $a_n \in \mathbb{Z}$ and $3 \mid a_n$ for all $n \in \mathbb{Z}_{\geq 0}$
To notice that $a_n \in \mathbb{Z}$, notice that $a_0 = x_1^0+x_2^0+x_3^0 = 1+1+1 = 3 \in \mathbb{Z}$, $a_1 = x_1+x_2+x_3 = 3$ by Vieta on sum of roots of $P(X)$ and $a_2 = x_1^2+x_2^2+x_3^2 = (x_1+x_2+x_3)^2-2(x_1x_2+x_1x_3+x_2x_3) = 3^2-2(0) = 9$ again by Vieta.
Now, notice that $a_{n+3} = 3a_{n+2}-a_n$. This means that if for some $k \in \mathbb{Z}_{\geq 0}$, $(a_k, a_{k+1},a_{k+2}) = (0,0,0)$ in $\mathbb{F}_{3}^3$ and are integers, then $a_{n+3} = 0$ in $\mathbb{F}_3$ too. Then just induct on $n$ to prove that $a_n \in 3\mathbb{Z}$ which follows by $a_0, a_1, a_2$ satisfying said property. $\blacksquare$ $\blacksquare$
$\textbf{Lemma 3: Ceiling Matches Recursive Sequence}$ $a_n = \lceil x_3^n \rceil$
To this end, we have the following claim which easily implies the lemma.
$\textbf{Claim:}$ $0 < x_1^n+x_2^n<1$ for all $n \geq 1$
$\textbf{Proof)}$
We will establish the two inequalities separately, which will heavily use the results that were established at the beginning which imply that $-1<x_1<0<x_2<1<2\sqrt{2} < x_3<3$ by the Intermediate Value Theorem on continuous function $P(X)$.
Firstly, notice that $x_1+x_2 > 0$ as $x_1+x_2+x_3 = 3$ and $x_3 < 3$. Therefore $|x_2|>|x_1|$ as $|x_2| = x_2, |x_1| = -x_1$, hence $x_1^n+x_2^n>0$ for all $n \in \mathbb{N}$, the result being clear for even $n$ and requiring the fact that $x_1^n+x_2^n = |x_2|^n-|x_1|^n>0$
Now, as for $x_1^n+x_2^n<1$, notice that if $n$ is odd, then $x_1^n+x_2^n < x_2^n < 1$, and if $n$ is even, $x_1^n+x_2^n \leq x_1^2+x_2^2 = 9-x_3^2 < 1$ as $x_3 > 2\sqrt{2}$ where the first inequality follows by the fact that $|x_1|, |x_2| < 1$.
This establishes both inequalities and the claim. $\blacksquare$
Now, notice that $x_3^n< x_1^n+x_2^n+x_3^n = a_n < x_3^n+1$ meaning that $a_n = \lceil x_3^n \rceil$ as $a_n \in \mathbb{Z}$ by $\textbf{Lemma 2}$. $\blacksquare$ $\blacksquare$
We know that $3 \mid a_n = \lceil x_3^n \rceil$ for $n \geq 1$ due to the $\textbf{Lemma 2}$ and $\textbf{Lemma 3}$ are therefore done!! $\blacksquare$ $\blacksquare$
minusonetwelth
17.06.2023 10:17
Didn't expect to solve a six on my first final, p4 gave me more trouble than this problem. The following solution uses Newton sums as the main idea. Claim 1: $f$ has a root on the interval $(-\frac{1}{\sqrt3},0)$.
Note that $f(-\frac{1}{\sqrt3})=-\frac{1}{\sqrt{3}^3}<0$ and $f(0)=1$. Thus, as $f$ is continuous, the function has a root that lies in $(-\frac{1}{\sqrt3},0)$ by the intermediate value theorem.
Claim 2: $f$ has a root on the interval $(\frac{1}{\sqrt3},\frac{1}{\sqrt[3]{3}})$.
Note that $f(\frac{1}{\sqrt3})>0$ and $f(-\frac{1}{\sqrt3})=\frac43-\sqrt[3]{3}<0$. The result follows as in the previous claim.
Now we notice that $f(3)=1>0$, so there must be another zero in $[\frac{1}{\sqrt[3]{3}},3)$. Thus, \[x_1\in (-\frac{1}{\sqrt3},0), x_2\in (\frac{1}{\sqrt3},\frac{1}{\sqrt[3]{3}}), x_3\in [\frac{1}{\sqrt[3]{3}},3)\]Now, notice that $x_1+x_2<\frac{1}{\sqrt[3]{3}}<1$. By Vieta's formula , $3> x_3=3-(x_1+x_2)>2$, so $\lceil x_3\rceil=3.$ Although we can prove inductively that the following idea works, we may as well cite the theorem all together:
For a polynomial
\[P(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0,\]let the $d$th Newton sum be
\[p_d=r_1^d+r_2^d+\ldots+r_n^d,\]where $r_1,\ldots,r_n$ are the complex roots of $P$. Then,
\begin{align*}
0&=a_np_1+a_{n-1}\\
&=a_np_2+a_{n-1}p_1+a_{n-2}\cdot 2\\
&=a_np_3+a_{n-1}p_2+a_{n-2}p_1+a_{n-3}\cdot 3\\
&\vdots
\end{align*}where $a_i=0$ if $a<0$.
Cleary, the first few cases $p_1=3,P_2=9,p_3=24$ are clear. Then, \[p_{k+1}=3p_k-p_{k-2}\]so $3\mid p_{k+1}$ by induction. As $x_1>-\frac{1}{\sqrt{3}}$ and $x_2>\frac{1}{\sqrt{3}}$, we have $x_1^n+x_2^n>0$. Also, $x_1^n+x_2^n<|\frac{1}{\sqrt{3}^n}|+\frac{1}{\sqrt[3]{3}^n}<1$ for $n\ge 2$. Hence \[p_n>x_3^n=p_n-(x_1^n-x_2^n)>p_n-1\]for all $n\ge 2$. Thus, $\lceil x_3^n\rceil=p_n$, and the conclusion follows.