Let $\alpha$ be the positive root of the equation $x^2+x=5$. Let $n$ be a positive integer number, and let $c_0,c_1,\ldots,c_n\in \mathbb{N}$ be such that $ c_0+c_1\alpha+c_2\alpha^2+\cdots+c_n\alpha^n=2015. $ a. Prove that $c_0+c_1+c_2+\cdots+c_n\equiv 2 \pmod{3}$. b. Find the minimum value of the sum $c_0+c_1+c_2+\cdots+c_n$.
Problem
Source:
Tags: algebra
26.03.2015 12:53
phuong wrote: Let $\alpha$ be the positive root of the equation $x^2+x=5$. Let $n$ be a positive integer number, and let $c_0,c_1,\ldots,c_n\in \mathbb{N}$ be such that $ c_0+c_1\alpha+c_2\alpha^2+\cdots+c_n\alpha^n=2015. $ a. Prove that $c_0+c_1+c_2+\cdots+c_n\equiv 2 \pmod{3}$. I suppose that, as usual here, $\mathbb N=\mathbb Z_{>0}$ Let $P(x)=\sum c_kx^k$ Since $P(\alpha)-2015=0$ and $\alpha\notin\mathbb Q$, we get $P(x)-2015=Q(x)(x^2+x-5)$ for some $Q(x)\in\mathbb Z[X]$ Setting $x=1$ in this equality, we get $P(1)\equiv 2\pmod 3$ phuong wrote: b. Find the minimum value of the sum $c_0+c_1+c_2+\cdots+c_n$. Writing $Q(x)=\sum_{k=0}^{n-2}a_kx^k$, we get : $c_0=2015-5a_0\ge 1$ and so $a_0\le 402$ $c_1=a_0-5a_1\ge 1$ and so $a_1\le 80$ $c_2=a_0+a_1-5a_2\ge 1$ and so $a_2\le 96$ $c_3=a_1+a_2-5a_3\ge 0$ and so $a_3\le 35$ $c_4=a_2+a_3-5a_4\ge 0$ and so $a_4\le 26$ $c_5=a_3+a_4-5a_5\ge 0$ and so $a_5\le 12$ $c_6=a_4+a_5-5a_6\ge 0$ and so $a_6\le 7$ $c_7=a_5+a_6-5a_7\ge 0$ and so $a_7\le 3$ $c_8=a_6+a_7-5a_8\ge 0$ and so $a_8\le 1$ ($a_8=2$ would imply $c_8=0$ and so $n<8$, impossible if $a_8>0$) And from there $a_k\le 0$ $\forall k\ge 9$ and so $\sum a_i\le 662$ We get also $P(1)=2015-3\sum a_i$ and so $P(1)\ge 29$ And, since $x^{10}+4x^9+5x^8$ $+4x^7+3x^6+x^5$ $+x^4+x^3+2x^2+2x+5$ $=(x^8+3x^7+7x^6$ $+12x^5+26x^4+35x^3$ $+96x^2+80x+402)$ $(x^2+x-5)+2015$ We get the answer : $\boxed{29}$
26.03.2015 13:42
I'm not sure whether $\mathbb{N}$ refers to the positive integers or nonnegative integers here. It doesn't change the result for part (a), but for part (b), we can get $c_0 + c_1 + \cdots + c_n = 20.$ Here is a solution for $\mathbb{N} = \{x \in \mathbb{Z} \mid x \ge 0\}.$ We will use the classical method of polynomial division: Consider the polynomial $P(x) = c_0 + c_1x + c_2x^2 + \cdots + c_nx^n.$ Since $P$ has integer coefficients, we may write $P(x) = \left(x^2 + x - 5\right)Q(x) + R(x)$ for polynomials $Q, R \in \mathbb{Z}[x]$ with $\deg R < 2.$ Hence, $R$ is a linear polynomial, so let us set $R(x) = Ax + B$ for some $A, B \in \mathbb{Z}.$ Notice that \[2015 = P(\alpha) = \left(\alpha^2 + \alpha - 5\right)Q(\alpha) + R(\alpha) = A\alpha + B.\] Therefore, if $A \ne 0$, we may write $\alpha = \tfrac{2015 - B}{A}$, but since $A$ and $B$ are integers, $\tfrac{2015 - B}{A}$ is rational, while $\alpha = \tfrac{\sqrt{21} - 1}{2}$ is certainly not. Hence, $A = 0$, whence we find that $B = 2015.$ Then observe that \[c_0 + c_1 + \cdots + c_n = P(1) = \left(1^2 + 1 - 5\right)Q(1) + R(1) = -3Q(1) + 2015 \equiv 2 \pmod{3},\] as desired. $\blacksquare$ Now, we will prove that the minimum possible value of $c_0 + c_1 + \cdots + c_n$ is $20.$ Let us write $Q(x) = q_0 + q_1x + q_2x^2 + \cdots$, and recall that $c_0 + c_1 + \cdots + c_n = P(1) = -3Q(1) + 2015.$ By multiplying $Q$ by $x^2 + x - 5$ and comparing coefficients, we find that \begin{align*} c_0 &= -5q_0 + 2015 \\ c_1 &= -5q_1 + q_0 \\ c_2 &= -5q_2 + q_1 + q_0 \\ c_3 &= -5q_3 + q_2 + q_1 \\ &\cdots \end{align*} Keeping in mind that the $c_i$’s and $q_i$’s are nonnegative integers, we obtain the following inequalities: \begin{align*} c_0 \ge 0 &\implies q_0 = \frac{2015 - c_0}{5} \le 403 \\ c_1 \ge 0 &\implies q_1 = \frac{q_0 - c_1}{5} \le 80 \\ c_2 \ge 0 &\implies q_2 = \frac{q_1 + q_0 - c_2}{5} \le 96 \\ c_3 \ge 0 &\implies q_3 = \frac{q_2 + q_1 - c_3}{5} \le 35 \\ c_4 \ge 0 &\implies q_4 = \frac{q_3 + q_2 - c_4}{5} \le 26 \\ c_5 \ge 0 &\implies q_5 = \frac{q_4 + q_3 - c_5}{5} \le 12 \\ c_6 \ge 0 &\implies q_6 = \frac{q_5 + q_4 - c_6}{5} \le 7 \\ c_7 \ge 0 &\implies q_7 = \frac{q_6 + q_5 - c_7}{5} \le 3 \\ c_8 \ge 0 &\implies q_8 = \frac{q_7 + q_6 - c_8}{5} \le 2 \\ c_9 \ge 0 &\implies q_9 = \frac{q_8 + q_7 - c_9}{5} \le 1 \end{align*} and for all $i > 9$, we have $q_i \le 0.$ Hence, $Q(1) = c_0 + c_1 + \cdots \le 403 + 80 + 96 + 35 + 26 + 12 + 7 + 3 + 2 + 1 = 665.$ It follows that $P(1) \ge -3(665) + 2015 = 20.$ Indeed, we an equality case exists: just take $Q(x) = x^9 + 2x^8 + 3x^7 + 7x^6 + 12x^5 + 26x^4 + 35x^3 + 96x^2 + 80x + 403.$ Therefore, the minimum possible value of $c_0 + c_1 + \cdots c_n$ is $20.$ $\square$
26.03.2015 15:16
$\mathbb{N}$ is the nonnegative integers set.