MHB This proves the claim.

  • Thread starter Thread starter Ackbach
  • Start date Start date
  • Tags Tags
    2017
Ackbach
Gold Member
MHB
Messages
4,148
Reaction score
93
Here is this week's POTW:

-----

Prove that every nonzero coefficient of the Taylor series of
\[
\left(1 - x + x^2\right) e^x
\]
about $x=0$ is a rational number whose numerator (in lowest terms) is either $1$ or a prime number.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!
 
Physics news on Phys.org
Congratulations to castor28 for his correct solution to this week's POTW, which is Problem A1 in the 2014 Putnam Archive. His solution follows:

[sp]
As the exponential series is absolutely convergent, we may multiply both series together.
If $a_n$ is the coefficient of $x^n$ in the resulting series, we have $a_0 = 1$, $a_1=0$, $a_2= \dfrac{1}{2}$. For $n>2$, we have:
$$
\begin{align*}\displaystyle
a_n &= \frac{1}{n!} - \frac{1}{(n-1)!} + \frac{1}{(n-2)!}\\
&= \frac{(n-1)^2}{n!}\\
&= \frac{n-1}{n(n-2)!}
\end{align*}
$$

and we must prove that, when this fraction is reduced to lowest terms, the numerator is $1$ or a prime number.

Writing $n = m+1$, we have:
$$\displaystyle
a_n = \frac{m}{(m+1)(m-1)!}
$$

We will write $\mathrm{N}(m)$ for the numerator of that reduced fraction. We must prove that this is $1$ or a prime.

The idea is to look at the prime divisors of $m$, and to estimate the number of occurrences of these in $(m-1)!$ to show that sufficient cancellation takes place.
We will use the well-known fact that, if $a$ and $b$ are integers with $a>1$ and $b> 0$, then $a^b > b$; furthermore, if $a>2$ or $b>2$, then we have the stronger relation $a^b > b+1$.

Case 1: $m = p$, $p$ prime

In this case, since $\gcd(p,(p-1)!) = \gcd(p, (p+1)) = 1$, no cancellation takes place and $\mathrm{N}(m)=p$.

Case 2: $m = p^k$, $p$ prime

The number of multiples of $p$ in the range $(1\dots m-1)$ is $p^{k-1}-1$. Note that these may include multiples of $p^2$, but we do not make use of this fact.
Using the fact mentioned above, we have:
$$
\begin{align*}\displaystyle
p^{k-1}&>k-1\\
p^{k-1}-1&>k-2\\
p^{k-1}-1 &\ge k-1
\end{align*}
$$
This shows that $p^{k-1}\mid (m-1)!$, and $\mathrm{N}(m)=1 \text{ or } p$.
As mentioned above, if $p>2$ or $k>2$, we have actually $p^{k-1}>k$, and $\mathrm{N}(m)=1$.
Note that case 1 is actually a particular case of this case.

Case 3: $m = qp^k$, $p$ prime, $q>1$, $\gcd(p,q)=1$

The number of multiples of $p$ in the range $(1\dots m-1)$ is $qp^{k-1}-1 > p^{k-1}-1 $. By comparison with case 2, we find that $p^k\mid (m-1)!$. As this holds for all primes that divide $m$, we conclude that $\mathrm{N}(m)=1$.

Rewriting all this in terms of $n$, the numerator of $a_n$ after reduction is:
  • $1$ for $n=0\text{ or }2$
  • $0$ for $n=1$
  • $2$ for $n=5$
  • $(n-1)$ when $(n-1)$ is prime
  • $1$ otherwise
[/sp]
 

Similar threads

Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
Back
Top