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 "2013 Canadian MO Problems/Problem 1"

(Created page with "==Problem == Determine all polynomials <math>P(x)</math> with real coefficients such that <cmath>(x+1)P(x-1)-(x-1)P(x)</cmath> is a constant polynomial. ==Solution== Le...")
 
 
(25 intermediate revisions by the same user not shown)
Line 12: Line 12:
 
<math>F(x)=(x+1)\sum_{i=0}^{n}(x-1)^ic_i-(x-1)\sum_{i=0}^{n}c_ix^i</math>
 
<math>F(x)=(x+1)\sum_{i=0}^{n}(x-1)^ic_i-(x-1)\sum_{i=0}^{n}c_ix^i</math>
  
−
<math>F(x)=\sum_{i=0}^{n}x(x-1)^ic_i+\sum_{i=0}^{n}(x-1)^ic_i-\sum_{i=0}^{n}c_ix^{i+1}+sum_{i=0}^{n}c_ix^i</math>
+
<math>F(x)=\sum_{i=0}^{n}x(x-1)^ic_i+\sum_{i=0}^{n}(x-1)^ic_i-\sum_{i=0}^{n}c_ix^{i+1}+\sum_{i=0}^{n}c_ix^i</math>
 +
 
 +
<math>\sum_{i=0}^{n}(x-1)^ic_i=\sum_{j=0}^{n}\left( \sum_{i=j}^{n}(-1)^{i-j}\binom{i}{i-j}c_i \right)x^j</math>
 +
 
 +
<math>\sum_{i=0}^{n}x(x-1)^ic_i=\sum_{j=0}^{n}\left( \sum_{i=j}^{n}(-1)^{i-j}\binom{i}{i-j}c_i \right)x^{j+1}</math>
 +
 
 +
<math>F(x)=\sum_{j=0}^{n}\left( \sum_{i=j}^{n}(-1)^{i-j}\binom{i}{i-j}c_i \right)x^j+\sum_{j=0}^{n}\left( \sum_{i=j}^{n}(-1)^{i-j}\binom{i}{i-j}c_i \right)x^{j+1}-\sum_{i=0}^{n}c_ix^{i+1}+\sum_{i=0}^{n}c_ix^i</math>
 +
 
 +
In order for the new polynomial <math>F(x)</math> to be a constant, all the coefficients in front of <math>x^i</math> for <math>i>1</math> need to be zero.
 +
 
 +
So we start by looking at the coefficient in front of <math>x^2</math>:
 +
 
 +
<math>\left( c_2-c_1+\sum_{i=2}^{n}(-1)^{i-2}\binom{i}{i-2}c_i+\sum_{i=1}^{n}(-1)^{i-1}\binom{i}{i-1}c_i \right)x^2</math>
 +
 
 +
Since <math>\sum_{i=1}^{n}(-1)^{i-1}\binom{i}{i-1}c_i=c_1+\sum_{i=2}^{n}(-1)^{i-1}\binom{i}{i-1}c_i</math>,
 +
 
 +
<math>\left( c_2-c_1+c_1+\sum_{i=2}^{n}(-1)^{i-2}\binom{i}{i-2}c_i+\sum_{i=2}^{n}(-1)^{i-1}\binom{i}{i-1}c_i \right)x^2</math>
 +
 
 +
<math>\left( c_2+\sum_{i=2}^{n}\left((-1)^{i-2}\binom{i}{i-2}+(-1)^{i-1}\binom{i}{i-1} \right)c_i\right)x^2</math>
 +
 
 +
We then evaluate the term of the sum when <math>i=2</math>:
 +
 
 +
<math>\left( c_2+(1-2)c_2+\sum_{i=3}^{n}\left((-1)^{i-2}\binom{i}{i-2}+(-1)^{i-1}\binom{i}{i-1} \right)c_i\right)x^2</math>
 +
 
 +
<math>\left(\sum_{i=3}^{n}\left((-1)^{i-2}\binom{i}{i-2}+(-1)^{i-1}\binom{i}{i-1} \right)c_i\right)x^2=0</math>
 +
 
 +
Note that since <math>c_0</math>, <math>c_1</math>, and <math>c_2</math> are not present in the expression before <math>x^2</math>, they can be anything and the coefficient in front of <math>x^2</math> is still zero because the expression before <math>x^3</math> also starts with <math>c_3</math>, and the expression before <math>x^4</math> also starts with <math>c_4</math> and so on...
 +
 
 +
In fact in matrix form when solving for <math>c_i</math> for for all <math>i</math>, it will look something like this:
 +
 
 +
<math>\begin{bmatrix}
 +
2 & -1 & 1 & -1 & 1 & -1 &\cdots & K_{0n}\\
 +
0 & 1 & -1 & 2 & -3 & 4 &  \cdots & K_{1n}\\
 +
0 & 0 & 0 & 0 & 2 & -5 & \cdots & K_{2n}\\
 +
0 & 0 & 0 & -1 & 2 & 0 & \cdots & K_{3n}\\
 +
0 & 0 & 0 & 0 & -2 & 5 & \cdots & K_{4n}\\
 +
0 & 0 & 0 & 0 & 0 & -3 & \cdots & K_{5n}\\
 +
\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\ddots &\vdots\\
 +
0 & 0 & 0& 0& 0& 0& \cdots & -n+2
 +
\end{bmatrix}
 +
\begin{bmatrix}c_0 \\c_1 \\c_2\\c_3\\c_4\\c_5\\ \vdots \\ c_n \end{bmatrix}
 +
=\begin{bmatrix}0 \\0 \\0\\0\\0\\0\\ \vdots \\ 0 \end{bmatrix}</math>
 +
 
 +
This matrix is singular because the 3nd row and the 4rd row also start at the 3rd column, then all coefficients <math>c_i</math> for <math>i \ge 3</math> need to be zero so that the coefficient in front of <math>x^2</math> is zero.
 +
 
 +
That is, <math>c_3=c_4=c_5=\cdots =c_n=0</math>.
 +
 
 +
So now we just need to find <math>c_1</math> and <math>c_2</math>, for that we look at the coefficient in front of <math>x</math> in <math>F(x)</math>:
 +
 
 +
<math>\left( c_1-c_0+\sum_{i=1}^{n}(-1)^{i-1}\binom{i}{i-1}c_i+\sum_{i=0}^{n}(-1)^{i}\binom{i}{i}c_i \right)x</math>
 +
 
 +
Since <math>c_i</math>=0 for <math>i \ge 3</math>:
 +
 
 +
<math>\left( c_1-c_0+\sum_{i=1}^{2}(-1)^{i-1}\binom{i}{i-1}c_i+\sum_{i=0}^{2}(-1)^{i}\binom{i}{i}c_i \right)x</math>
 +
 
 +
<math>\left( c_1-c_0+\binom{1}{0}c_1-\binom{2}{1}c_2+c_0-c_1+c_2\right)x</math>
 +
 
 +
<math>\left( c_1-c_0+c_1-2c_2+c_0-c_1+c_2\right)x</math>
 +
 
 +
<math>\left(c_1-c_2\right)x</math>
 +
 
 +
Therefore <math>c_1-c_2=0</math>, thus <math>c_1=c_2</math> satisfies the condition for <math>F(x)</math> to be a constant polynomial.
 +
 
 +
So we can set <math>c_1=c_2=A</math> and <math>c_0=B</math>, and all the polynomials <math>P(x)</math> will be in the form:
 +
 
 +
<math>P(x)=Ax^2+Ax+B</math> where <math>A,B \in \mathbb{R}</math>
  
 
~Tomas Diaz. orders@tomasdiaz.com
 
~Tomas Diaz. orders@tomasdiaz.com
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Latest revision as of 02:36, 27 November 2023

Problem

Determine all polynomials $P(x)$ with real coefficients such that \[(x+1)P(x-1)-(x-1)P(x)\] is a constant polynomial.

Solution

Let $F(x)=(x+1)P(x-1)-(x-1)P(x)$

$P(x)=\sum_{i=0}^{n}c_ix^i$

$F(x)=(x+1)\sum_{i=0}^{n}(x-1)^ic_i-(x-1)\sum_{i=0}^{n}c_ix^i$

$F(x)=\sum_{i=0}^{n}x(x-1)^ic_i+\sum_{i=0}^{n}(x-1)^ic_i-\sum_{i=0}^{n}c_ix^{i+1}+\sum_{i=0}^{n}c_ix^i$

$\sum_{i=0}^{n}(x-1)^ic_i=\sum_{j=0}^{n}\left( \sum_{i=j}^{n}(-1)^{i-j}\binom{i}{i-j}c_i \right)x^j$

$\sum_{i=0}^{n}x(x-1)^ic_i=\sum_{j=0}^{n}\left( \sum_{i=j}^{n}(-1)^{i-j}\binom{i}{i-j}c_i \right)x^{j+1}$

$F(x)=\sum_{j=0}^{n}\left( \sum_{i=j}^{n}(-1)^{i-j}\binom{i}{i-j}c_i \right)x^j+\sum_{j=0}^{n}\left( \sum_{i=j}^{n}(-1)^{i-j}\binom{i}{i-j}c_i \right)x^{j+1}-\sum_{i=0}^{n}c_ix^{i+1}+\sum_{i=0}^{n}c_ix^i$

In order for the new polynomial $F(x)$ to be a constant, all the coefficients in front of $x^i$ for $i>1$ need to be zero.

So we start by looking at the coefficient in front of $x^2$:

$\left( c_2-c_1+\sum_{i=2}^{n}(-1)^{i-2}\binom{i}{i-2}c_i+\sum_{i=1}^{n}(-1)^{i-1}\binom{i}{i-1}c_i \right)x^2$

Since $\sum_{i=1}^{n}(-1)^{i-1}\binom{i}{i-1}c_i=c_1+\sum_{i=2}^{n}(-1)^{i-1}\binom{i}{i-1}c_i$,

$\left( c_2-c_1+c_1+\sum_{i=2}^{n}(-1)^{i-2}\binom{i}{i-2}c_i+\sum_{i=2}^{n}(-1)^{i-1}\binom{i}{i-1}c_i \right)x^2$

$\left( c_2+\sum_{i=2}^{n}\left((-1)^{i-2}\binom{i}{i-2}+(-1)^{i-1}\binom{i}{i-1} \right)c_i\right)x^2$

We then evaluate the term of the sum when $i=2$:

$\left( c_2+(1-2)c_2+\sum_{i=3}^{n}\left((-1)^{i-2}\binom{i}{i-2}+(-1)^{i-1}\binom{i}{i-1} \right)c_i\right)x^2$

$\left(\sum_{i=3}^{n}\left((-1)^{i-2}\binom{i}{i-2}+(-1)^{i-1}\binom{i}{i-1} \right)c_i\right)x^2=0$

Note that since $c_0$, $c_1$, and $c_2$ are not present in the expression before $x^2$, they can be anything and the coefficient in front of $x^2$ is still zero because the expression before $x^3$ also starts with $c_3$, and the expression before $x^4$ also starts with $c_4$ and so on...

In fact in matrix form when solving for $c_i$ for for all $i$, it will look something like this:

$\begin{bmatrix} 2 & -1 & 1 & -1 & 1 & -1 &\cdots & K_{0n}\\ 0 & 1 & -1 & 2 & -3 & 4 & \cdots & K_{1n}\\ 0 & 0 & 0 & 0 & 2 & -5 & \cdots & K_{2n}\\ 0 & 0 & 0 & -1 & 2 & 0 & \cdots & K_{3n}\\ 0 & 0 & 0 & 0 & -2 & 5 & \cdots & K_{4n}\\ 0 & 0 & 0 & 0 & 0 & -3 & \cdots & K_{5n}\\ \vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\ddots &\vdots\\ 0 & 0 & 0& 0& 0& 0& \cdots & -n+2 \end{bmatrix} \begin{bmatrix}c_0 \\c_1 \\c_2\\c_3\\c_4\\c_5\\ \vdots \\ c_n \end{bmatrix} =\begin{bmatrix}0 \\0 \\0\\0\\0\\0\\ \vdots \\ 0 \end{bmatrix}$

This matrix is singular because the 3nd row and the 4rd row also start at the 3rd column, then all coefficients $c_i$ for $i \ge 3$ need to be zero so that the coefficient in front of $x^2$ is zero.

That is, $c_3=c_4=c_5=\cdots =c_n=0$.

So now we just need to find $c_1$ and $c_2$, for that we look at the coefficient in front of $x$ in $F(x)$:

$\left( c_1-c_0+\sum_{i=1}^{n}(-1)^{i-1}\binom{i}{i-1}c_i+\sum_{i=0}^{n}(-1)^{i}\binom{i}{i}c_i \right)x$

Since $c_i$=0 for $i \ge 3$:

$\left( c_1-c_0+\sum_{i=1}^{2}(-1)^{i-1}\binom{i}{i-1}c_i+\sum_{i=0}^{2}(-1)^{i}\binom{i}{i}c_i \right)x$

$\left( c_1-c_0+\binom{1}{0}c_1-\binom{2}{1}c_2+c_0-c_1+c_2\right)x$

$\left( c_1-c_0+c_1-2c_2+c_0-c_1+c_2\right)x$

$\left(c_1-c_2\right)x$

Therefore $c_1-c_2=0$, thus $c_1=c_2$ satisfies the condition for $F(x)$ to be a constant polynomial.

So we can set $c_1=c_2=A$ and $c_0=B$, and all the polynomials $P(x)$ will be in the form:

$P(x)=Ax^2+Ax+B$ where $A,B \in \mathbb{R}$

~Tomas Diaz. orders@tomasdiaz.com

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_Canadian_MO_Problems/Problem_1&oldid=206089"