uniolympiads Ελληνικά

IMC 2002, Day 2, Problem 3

For each n≥1n \ge 1 let

an=∑k=0∞knk!,bn=∑k=0∞(−1)kknk!.a_n = \sum_{k=0}^{\infty} \frac{k^n}{k!}, \quad b_n = \sum_{k=0}^{\infty} (-1)^k \frac{k^n}{k!}.

Show that an⋅bna_n \cdot b_n is an integer.

Original from the official PDFFor each n ≥ 1 let a n = ∞ X k n k=0 k! , b n = ∞ X (−1) k k=0 Show that a n · b n is an integer. k n . k!

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. We prove by induction on nn that an/ea_n/e and bneb_ne are integers, we prove this for n=0n=0 as well. (For n=0n=0, the term 000^0 in the definition of the sequences must be replaced by 1.)

From the power series of exe^x, an=e1=ea_n=e^1=e and bn=e−1=1/eb_n=e^{-1}=1/e.

Suppose that for some n≥0n\ge0, a0,a1,…,ana_0,a_1,\dots,a_n and b0,b1,...bnb_0,b_1,...b_n are all multipliers of ee and 1/e1/e, respectively. Then, by the binomial theorem,

an+1=∑k=0n(k+1)n+1(k+1)!=∑k=0∞(k+1)nk!=∑k=0∞∑m=0n(nm)kmk!==∑m=0n(nm)∑k=0∞kmk!=∑m=0n(nm)am\begin{aligned}a_{n+1}&=\sum_{k=0}^{n}\frac{(k+1)^{n+1}}{(k+1)!}=\sum_{k=0}^{\infty}\frac{(k+1)^n}{k!}=\sum_{k=0}^{\infty}\sum_{m=0}^{n}\binom{n}{m}\frac{k^m}{k!}=\\&=\sum_{m=0}^{n}\binom{n}{m}\sum_{k=0}^{\infty}\frac{k^m}{k!}=\sum_{m=0}^{n}\binom{n}{m}a_m\end{aligned}
and similarly
bn+1=∑k=0n(−1)k+1(k+1)n+1(k+1)!=−∑k=0∞(−1)k(k+1)nk!==−∑k=0∞(−1)k∑m=0n(nm)kmk!=−∑m=0n(nm)∑k=0∞(−1)kkmk!=−∑m=0n(nm)bm.\begin{aligned}b_{n+1}&=\sum_{k=0}^{n}(-1)^{k+1}\frac{(k+1)^{n+1}}{(k+1)!}=-\sum_{k=0}^{\infty}(-1)^k\frac{(k+1)^n}{k!}=\\&=-\sum_{k=0}^{\infty}(-1)^k\sum_{m=0}^{n}\binom{n}{m}\frac{k^m}{k!}=-\sum_{m=0}^{n}\binom{n}{m}\sum_{k=0}^{\infty}(-1)^k\frac{k^m}{k!}=-\sum_{m=0}^{n}\binom{n}{m}b_m.\end{aligned}

The numbers an+1a_{n+1} and bn+1b_{n+1} are expressed as linear combinations of the previous elements with integer coefficients which finishes the proof.

Transcribed from the official solutions, page 2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?