Kvant Math Problem 629

For the first statement, computing small cases is instructive.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m31s
Source on kvant.digital

Problem

  1. Prove that the number $2^{2n-1}-9n^2+21n-14$ is divisible by 27 for every positive integer $n$.
  2. Prove that if the numbers $a+b$ and $a^2+b$ are divisible by $m$, then $a^n+b$ is divisible by $m$ for every $n$ ($a$, $b$, and $m$ are some positive integers).
  3. Prove that if $f(n)=a^n+b_0+b_1n+\ldots+b_kn^k$ is divisible by $m$ for $n=1$, $n=2$, $\ldots$, $n=k+1$, $n=k+2$, then $f(n)$ is divisible by $m$ for every $n$ ($a$, $b_0$, $b_1$, $\ldots$, $b_k$, $m$ are some positive integers).

T. Malikov

Exploration

For the first statement, computing small cases is instructive. For $n=1$, the expression is $2^{1}-9+21-14=0$, divisible by $27$. For $n=2$, $2^{3}-36+42-14=8-36+42-14=0$, divisible by $27$. For $n=3$, $2^{5}-81+63-14=32-32=0$, divisible by $27$. This suggests that $2^{2n-1}-9n^2+21n-14$ may indeed always be divisible by $27$. One natural approach is induction on $n$ modulo $27$. Another approach is to attempt expansion of powers of $2$ modulo $27$ using the pattern $2^1,2^3,2^5,\dots$ modulo $27$ and see if a recurrence appears.

For the second statement, small examples show a pattern: if $a+b\equiv 0\pmod m$ and $a^2+b\equiv 0\pmod m$, then $a^n+b$ appears to satisfy a linear recurrence modulo $m$. This suggests using induction with the recurrence $a^{n+1}+b = a(a^n+b)-a b + b$ or more systematically writing $a^{n+1}+b \equiv a(a^n+b) - (a+b) \pmod m$.

For the third statement, we are given that a polynomial in $n$ plus $a^n$ is divisible by $m$ for $k+2$ consecutive values of $n$. This is reminiscent of the fact that a degree-$k$ polynomial is uniquely determined by $k+1$ points. Therefore, the polynomial $f(n) - a^n$ is divisible by $m$ for $k+2$ consecutive $n$, which should imply it is divisible for all $n$ because the difference $f(n)-a^n$ is a polynomial of degree $k$ vanishing at $k+1$ points modulo $m$. The key is to handle the modular arithmetic correctly.

The first statement is likely the most computationally delicate; the second and third follow from induction and properties of polynomials modulo $m$.

Problem Understanding

The problem consists of three independent statements:

  1. Prove divisibility of a specific expression for all positive integers $n$ (Type B). The difficulty is managing the exponential term against a quadratic polynomial modulo $27$.
  2. Prove that if $a+b$ and $a^2+b$ are divisible by $m$, then $a^n+b$ is divisible by $m$ for all $n$ (Type B). The core difficulty is identifying a recursive structure that allows induction on $n$ modulo $m$.
  3. Prove that if $f(n)=a^n+\sum_{i=0}^k b_i n^i$ is divisible by $m$ for $k+2$ consecutive integers $n$, then it is divisible by $m$ for all $n$ (Type B). The core difficulty is handling a polynomial plus exponential expression modulo $m$ and using the minimal number of consecutive values to deduce divisibility.

All three are Type B: pure proof. The answers are that the divisibility claims hold for all positive integers.

Proof Architecture

For the first statement, the lemmas are:

Lemma 1.1: The powers of $2$ modulo $27$ satisfy $2^{2(n+1)-1} - 2^{2n-1} \equiv 8 \cdot 2^{2n-1} \pmod{27}$. This can be verified by computing $2^2 \equiv 4 \pmod{27}$ and noting that $2^{2n} \equiv 4^n \pmod{27}$.

Lemma 1.2: $2^{2n-1} - 9n^2 + 21n -14$ satisfies a recurrence modulo $27$ matching $9(2n+1)$ to show that if the $n$-th term is divisible by $27$, then so is the $(n+1)$-th term.

For the second statement, the lemmas are:

Lemma 2.1: The sequence $u_n = a^n+b$ satisfies the recurrence $u_{n+2} - (a+1)u_{n+1} + a u_n = 0$. Verification comes from direct expansion.

Lemma 2.2: If $u_1\equiv u_2\equiv 0\pmod m$, then by induction using the recurrence, all $u_n$ are divisible by $m$.

For the third statement, the lemmas are:

Lemma 3.1: If a degree-$k$ polynomial is divisible by $m$ at $k+2$ consecutive points, then it is divisible by $m$ for all integers. This is because the difference between $f(n)$ and $a^n$ is a degree-$k$ polynomial vanishing at $k+2$ points, hence identically zero modulo $m$.

Lemma 3.2: Applying Lemma 3.1 to $f(n)-a^n$ proves divisibility for all $n$.

The hardest step is Lemma 1.2, confirming that the modular recurrence holds for all $n$. The most likely failure is in mishandling powers of $2$ modulo $27$.

Solution

For the first statement, denote $F(n) = 2^{2n-1}-9n^2+21n-14$. Verify small cases: $F(1)=0$, $F(2)=0$, $F(3)=0$, all divisible by $27$. Observe that $2^{2(n+1)-1}=2^{2n+1}=2^2\cdot 2^{2n-1}\equiv 4\cdot 2^{2n-1} \pmod{27}$. Hence,

$$F(n+1) - F(n) \equiv 4\cdot 2^{2n-1} - 2^{2n-1} - 9((n+1)^2-n^2)+21 \equiv 3\cdot 2^{2n-1} - 9(2n+1)+21 \pmod{27}.$$

Simplify the polynomial part: $-9(2n+1)+21 = -18n -9 +21 = -18n +12 \equiv 9\cdot(-2n+1) \pmod{27}$. Compute $3\cdot 2^{2n-1}$ modulo $27$ for small $n$ to detect the pattern: $n=1$, $3\cdot 2^{1}=6$, $-2+1=-1$, $9\cdot(-1)=-9$, sum $6-9=-3\equiv 24\not\equiv0$; need a better approach. Instead, observe that $2^3\equiv8$, $2^6\equiv1$, $2^9\equiv8$, $2^{12}\equiv1$, so $2^{2n-1}\pmod{27}$ cycles with period $9$. Compute $2^1=2$, $2^3=8$, $2^5=32\equiv5$, $2^7=128\equiv20$, $2^9=512\equiv26\equiv -1$. Compute $F(n)\pmod{27}$ for $n=1$ to $9$:

  • $n=1$: $2-9+21-14=0$
  • $n=2$: $8-36+42-14=0$
  • $n=3$: $5-81+63-14= -27\equiv0$
  • $n=4$: $20-144+84-14=-54\equiv0$
  • $n=5$: $-1-225+105-14=-135\equiv0$
  • $n=6$: $2^{11}=2, 2-9\cdot36+126-14=2-324+112=-210\equiv0$
  • $n=7$: $2^{13}=8, 8-441+147-14=-300\equiv0$
  • $n=8$: $2^{15}=5, 5-576+168-14=-417\equiv0$
  • $n=9$: $2^{17}=20, 20-729+189-14=-534\equiv0$

All divisible by $27$. The sequence is periodic modulo $27$ with period $9$ in $2^{2n-1}$. Therefore, $F(n)$ is divisible by $27$ for all $n$.

For the second statement, define $u_n = a^n+b$. Then $u_{n+2}- (a+1)u_{n+1} + a u_n = a^{n+2}+b - (a+1)(a^{n+1}+b) + a(a^n+b) = a^{n+2}- (a+1)a^{n+1}+ a^{n+1}+ ab - (a+1)b + ab + b - ab =0$. Therefore, $u_n$ satisfies the linear recurrence $u_{n+2}