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 "1975 USAMO Problems/Problem 3"

(→‎Problem)
m (→‎Solution 1)
 
(8 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
If <math>P(x)</math> denotes a polynomial of degree <math>n</math> such that <cmath>P(k)=k/(k+1)</cmath> for <math>k=0,1,2,\ldots,n</math>, determine <math>P(n+1)</math>.
+
If <math>P(x)</math> denotes a polynomial of degree <math>n</math> such that <cmath>P(k)=\frac{k}{k+1}</cmath> for <math>k=0,1,2,\ldots,n</math>, determine <math>P(n+1)</math>.
  
−
==Solution==
+
==Solution 1==
−
Let <math>Q(x) = (x+1)P(x) - x</math>. Clearly, <math>Q(x)</math> has a degree of <math>n+1</math>.  
+
Let <math>Q(x) = (x+1)P(x) - x</math>, and clearly, <math>Q(x)</math> has a degree of <math>n+1</math>.  
  
−
Then, for <math>k=0,1,2,\ldots,n</math>, <math>Q(k) = (k+1)P(k) - k = (k+1)\dfrac{k}{k+1} - k = 0</math>.  
+
Then, for <math>k=0,1,2,\ldots,n</math>, <math>Q(k) = (k+1)P(k) - k = (k+1)\cdot \dfrac{k}{k+1} - k = 0</math>.  
  
 
Thus, <math>k=0,1,2,\ldots,n</math> are the roots of <math>Q(x)</math>.  
 
Thus, <math>k=0,1,2,\ldots,n</math> are the roots of <math>Q(x)</math>.  
  
−
Since these are all <math>n+1</math> of the roots, we can write <math>Q(x)</math> as: <math>Q(x) = K(x)(x-1)(x-2) \cdots (x-n)</math> where <math>K</math> is a constant.  
+
Since these are all <math>n+1</math> of the roots of the <math>n+1^{\text{th}}</math> degree polynomial, by the [[Factor Theorem]], we can write <math>Q(x)</math> as <cmath>Q(x) = c(x)(x-1)(x-2) \cdots (x-n)</cmath> where <math>c</math> is a constant.  
  
−
Thus, <math>(x+1)P(x) - x = K(x)(x-1)(x-2) \cdots (x-n)</math>
+
Thus, <cmath>(x+1)P(x) - x = c(x)(x-1)(x-2) \cdots (x-n).</cmath>
  
−
Plugging in <math>x = -1</math> gives:  
+
We plug in <math>x = -1</math> to cancel the <math>(x+1)P(x)</math> and find <math>c</math>:  
  
−
<math>(-1+1)P(-1) - (-1) = K(-1)(-1-1)(-1-2) \cdots (-1-n)</math>
+
<cmath>\begin{align*}
 +
-(-1) &= c(-1)(-1-1)(-1-2) \cdots (-1-n) \\
 +
1 &= c(-1)^{n+1}(1)(2) \cdots (n+1) \\
 +
c &= (-1)^{n+1}\dfrac{1}{(n+1)!} \\
 +
\end{align*}</cmath>
  
−
<math>1 = K(-1)^{n+1}(1)(2) \cdots (n+1)</math>
+
Finally, plugging in <math>x = n+1</math> to find <math>P(n+1)</math> gives:
  
−
<math>K = (-1)^{n+1}\dfrac{1}{(n+1)!}</math>
+
<cmath>\begin{align*}
 +
Q(n+1)&=(n+2)P(n+1)-(n+1)\\
 +
(-1)^{n+1}\dfrac{1}{(n+1)!}\cdot(n+1)! &=(n+2)P(n+1)-(n+1)\\
 +
(-1)^{n+1}&=(n+2)P(n+1)-(n+1)\\
 +
(-1)^{n+1}+(n+1)&=(n+2)P(n+1)\\
 +
P(n+1) &= \dfrac{(-1)^{n+1} + (n+1)}{n+2}\\
 +
\end{align*}</cmath>
  
−
Finally, plugging in <math>x = n+1</math> gives:
+
If <math>n</math> is even, this simplifies to <math>P(n+1) = \dfrac{n}{n+2}</math>. If <math>n</math> is odd, this simplifies to <math>P(n+1) = 1</math>. <math>\Box</math>
  
−
<math>(n+1+1)P(n+1) - (n+1) =</math> <math>(-1)^{n+1}\dfrac{1}{(n+1)!}(n+1)(n+1-1)(n+1-2) \cdots (n+1-n)</math>
+
~Edits by BakedPotato66
−
 
 
−
<math>(n+2)P(n+1) = (-1)^{n+1}\dfrac{1}{(n+1)!}\cdot(n+1)! + (n+1)</math>
 
−
 
 
−
<math>(n+2)P(n+1) = (-1)^{n+1} + (n+1)</math>
 
−
 
 
−
<math>P(n+1) = \dfrac{(-1)^{n+1} + (n+1)}{n+2}</math>
 
−
 
 
−
If <math>n</math> is even, this simplifies to <math>P(n+1) = \dfrac{n}{n+2}</math>. If <math>n</math> is odd, this simplifies to <math>P(n+1) = 1</math>.
 
  
 
==Solution 2==
 
==Solution 2==
 
It is fairly natural to use Lagrange's Interpolation Formula on this problem:
 
It is fairly natural to use Lagrange's Interpolation Formula on this problem:
  
−
<math>\begin{align}
+
<cmath>\begin{align*}
−
P(n+1) &= \sum_{k=0}^n \frac{k}{k+1} \prod_{j \text{not} k} \frac{n+1-j}{k-j} \\
+
P(n+1) &= \sum_{k=0}^n \frac{k}{k+1} \prod_{j \ne k} \frac{n+1-j}{k-j} \\
−
&= \sum_{k=0}^n \frac{k}{k+1} \cdot \frac{\frac{(n+1)!}{n+1-k}}{k(k-1)(k-2) \dots 1\cdot (-1)(-2) \dots (k-n)}\\
+
&= \sum_{k=0}^n \frac{k}{k+1} \cdot \frac{\frac{(n+1)!}{n+1-k}}{k(k-1)(k-2) \dots 1\cdot (-1)(-2) \dots (k-n)} \\
 
&= \sum_{k=0}^n \frac{k}{k+1} (-1)^{n-k}\cdot \frac{(n+1)!}{k!(n+1-k)!} \\
 
&= \sum_{k=0}^n \frac{k}{k+1} (-1)^{n-k}\cdot \frac{(n+1)!}{k!(n+1-k)!} \\
 
&= \sum_{k=0}^n (-1)^{n-k} \binom{n+1}{k} - \sum_{k=0}^n \frac{(n+1)!(-1)^{n-k}}{(k+1)!(n+1-k)!} \\
 
&= \sum_{k=0}^n (-1)^{n-k} \binom{n+1}{k} - \sum_{k=0}^n \frac{(n+1)!(-1)^{n-k}}{(k+1)!(n+1-k)!} \\
−
&= -(\sum_{k=0}^{n+1} (-1)^{n+1-k} \binom{n+1}{k} - 1) + \frac{1}{n+2} \cdot \sum_{k=0}^n (-1)^{n+1-k} \binom{n+2}{k+1} \\
+
&= -\left(\sum_{k=0}^{n+1} (-1)^{n+1-k} \binom{n+1}{k} - 1\right) + \frac{1}{n+2} \cdot \sum_{k=0}^n (-1)^{n+1-k} \binom{n+2}{k+1} \\
−
&= 1 + \frac{1}{n+2} (\sum_{k=-1}^{n+1} (-1)^{n+2 - (k+1)} \binom{n+2}{k+1} - (-1)^{n+2} - 1) \\
+
&= 1 + \frac{1}{n+2} \left(\sum_{k=-1}^{n+1} (-1)^{n+2 - (k+1)} \binom{n+2}{k+1} - (-1)^{n+2} - 1\right) \\
 
&= \boxed{1 - \frac{(-1)^n + 1}{n+2}}
 
&= \boxed{1 - \frac{(-1)^n + 1}{n+2}}
−
\end{align}</math>
+
\end{align*}</cmath>
 +
through usage of the Binomial Theorem. <math>\square</math>
  
−
through usage of the Binomial Theorem.
+
~lpieleanu (minor editing and reformatting)
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Latest revision as of 17:29, 8 January 2024

Problem

If $P(x)$ denotes a polynomial of degree $n$ such that \[P(k)=\frac{k}{k+1}\] for $k=0,1,2,\ldots,n$, determine $P(n+1)$.

Solution 1

Let $Q(x) = (x+1)P(x) - x$, and clearly, $Q(x)$ has a degree of $n+1$.

Then, for $k=0,1,2,\ldots,n$, $Q(k) = (k+1)P(k) - k = (k+1)\cdot \dfrac{k}{k+1} - k = 0$.

Thus, $k=0,1,2,\ldots,n$ are the roots of $Q(x)$.

Since these are all $n+1$ of the roots of the $n+1^{\text{th}}$ degree polynomial, by the Factor Theorem, we can write $Q(x)$ as \[Q(x) = c(x)(x-1)(x-2) \cdots (x-n)\] where $c$ is a constant.

Thus, \[(x+1)P(x) - x = c(x)(x-1)(x-2) \cdots (x-n).\]

We plug in $x = -1$ to cancel the $(x+1)P(x)$ and find $c$:

\begin{align*} -(-1) &= c(-1)(-1-1)(-1-2) \cdots (-1-n) \\ 1 &= c(-1)^{n+1}(1)(2) \cdots (n+1) \\ c &= (-1)^{n+1}\dfrac{1}{(n+1)!} \\ \end{align*}

Finally, plugging in $x = n+1$ to find $P(n+1)$ gives:

\begin{align*} Q(n+1)&=(n+2)P(n+1)-(n+1)\\ (-1)^{n+1}\dfrac{1}{(n+1)!}\cdot(n+1)! &=(n+2)P(n+1)-(n+1)\\ (-1)^{n+1}&=(n+2)P(n+1)-(n+1)\\ (-1)^{n+1}+(n+1)&=(n+2)P(n+1)\\ P(n+1) &= \dfrac{(-1)^{n+1} + (n+1)}{n+2}\\ \end{align*}

If $n$ is even, this simplifies to $P(n+1) = \dfrac{n}{n+2}$. If $n$ is odd, this simplifies to $P(n+1) = 1$. $\Box$

~Edits by BakedPotato66

Solution 2

It is fairly natural to use Lagrange's Interpolation Formula on this problem:

\begin{align*} P(n+1) &= \sum_{k=0}^n \frac{k}{k+1} \prod_{j \ne k} \frac{n+1-j}{k-j} \\ &= \sum_{k=0}^n \frac{k}{k+1} \cdot \frac{\frac{(n+1)!}{n+1-k}}{k(k-1)(k-2) \dots 1\cdot (-1)(-2) \dots (k-n)} \\ &= \sum_{k=0}^n \frac{k}{k+1} (-1)^{n-k}\cdot \frac{(n+1)!}{k!(n+1-k)!} \\ &= \sum_{k=0}^n (-1)^{n-k} \binom{n+1}{k} - \sum_{k=0}^n \frac{(n+1)!(-1)^{n-k}}{(k+1)!(n+1-k)!} \\ &= -\left(\sum_{k=0}^{n+1} (-1)^{n+1-k} \binom{n+1}{k} - 1\right) + \frac{1}{n+2} \cdot \sum_{k=0}^n (-1)^{n+1-k} \binom{n+2}{k+1} \\ &= 1 + \frac{1}{n+2} \left(\sum_{k=-1}^{n+1} (-1)^{n+2 - (k+1)} \binom{n+2}{k+1} - (-1)^{n+2} - 1\right) \\ &= \boxed{1 - \frac{(-1)^n + 1}{n+2}} \end{align*} through usage of the Binomial Theorem. $\square$

~lpieleanu (minor editing and reformatting)

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

See Also

1975 USAMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1975_USAMO_Problems/Problem_3&oldid=210207"