Putnam 2025, Problem A-6

Let \( b_0 = 0 \) and, for \( n \geq 0 \), define \( b_{n+1} = 2b_n^2 + b_n + 1 \). For each \( k \geq 1 \), show that \( b_{2k+1} - 2b_{2k} \) is divisible by \( 2^{2k+2} \) but not by \( 2^{2k+3} \).

Solution:
**First solution.** As in the problem statement, assume throughout that \( k \geq 1 \). For \( m \geq 2 \) even and \( n \geq 0 \), define
\[
c_{m,n} := b_{m+n} - b_n, \quad d_{m,n} := 2(b_{m+n} + b_n) + 1;
\]
since \( b_0 = 0 \), we have
\[
b_{2k+1} - 2b_{2k} = c_{2k,2k} - c_{2k,0}.
\]
By induction on \( n \), we have \( b_n \equiv n \pmod{2} \); hence \( d_{m,n} \equiv 1 \pmod{4} \) (because \( m \) is even). By writing
\[
c_{m,n+1} = 2b_{m+n}^2 + b_{m+n} - 2b_n^2 - b_n = c_{m,n} d_{m,n},
\]
we obtain \( c_{m,n} = c_{m,0} D_{m,n} \) for \( D_{m,n} := \prod_{i=0}^{n-1} d_{m,i} \). For \( n \) a positive integer, let \( v_2(n) \) denote the 2-adic valuation of \( n \), i.e., the exponent of 2 in the prime factorization of \( n \). We prove \( v_2(c_{2k,i}) = k + 1 \) by immediately reducing to the case \( i = 0 \), then inducting on \( k \). For \( k = 1 \) we compute that \( c_{2,0} = 4 \). For \( k > 1 \), write
\[
c_{2k,0} = c_{2k-1,2k-1} + c_{2k-1,0} = c_{2k-1,0}(D_{2k-1,0} + 1);
\]
since \( D_{2k-1,0} \equiv 1 \pmod{4} \), \( v_2(D_{2k-1,0} + 1) = 1 \). Since \( b_{2k+1} - 2b_{2k} = c_{2k,0}(D_{2k,0} - 1) \), it will now suffice to check that \( v_2(D_{2k,0} - 1) = k + 1 \). We first note that since \( v_2(c_{2k,i}) = v_2(c_{2k,0}) = k + 1 \), we have \( b_{2k+i} - b_i \equiv 0 \pmod{2^{k+1}} \) and so \( d_{2k,i} \equiv 4b_i + 1 \pmod{2^{k+2}} \). Consequently, for \( A_n := \prod_{i=0}^{n-1} (4b_i + 1) \), we have \( D_{2k,0} \equiv A_{2k} \pmod{2^{k+2}} \); we thus have
\[
v_2(D_{2k,0} - 1) = k + 1 \Longleftrightarrow v_2(A_{2k} - 1) = k + 1.
\]
We prove that \( v_2(A_{2k} - 1) = k + 1 \) by induction on \( k \). For \( k = 1 \) we compute that \( A_1 = 5 \). For \( k > 1 \), we use the congruence \( b_{2k-1+i} \equiv b_i \pmod{2^k} \) to argue that
\[
A_k \equiv \prod_{i=0}^{2^{k-1}-1} (4b_i + 1)^2 = A_{k-1}^2 \pmod{2^{k+2}}.
\]
Writing \( A_{k-1} = 1 + 2^k m \) for some odd integer \( m \), we see that \( A_{k-1}^2 \equiv 1 + 2^{k+1} m \pmod{2^{k+2}} \), proving the claim.

**Remark.** One can similarly show that \( v_2(c_{m,n}) = v_2(m) + 1 \) for any even \( m \).

**Second solution.** (suggested by Victor Lie) Define \( f(x) = 2x^2 + x + 1 \), so that \( b_{n+1} = f(b_n) \) for \( n \geq 0 \). Let \( f_n \) be the \( n \)-fold composition of \( f \), so that \( f_1 = f \), \( f_{n+1} = f_n \circ f = f \circ f_n \), and \( b_{2k} = f_{2k}(0) \).

We first observe that for \( k \geq 1 \),
\[
f_{2k}(x) \equiv x \pmod{4, x^3} :
\]
for \( k = 1 \), we calculate directly that
\[
f_2(x) \equiv 4 + 5x + 12x^2 \pmod{x^3}
\]
and then the claim is immediate by induction. We next prove by induction on \( k \) that for \( k \geq 1 \),
\[
f_{2k}(x) \equiv 2^{k+1} + (1 + 2^{k+1})x \pmod{2^{k+2}, x^2}.
\]
The case \( k = 1 \) is again clear. To go from \( k \) to \( k + 1 \), write \( f_{2k}(x) = A + Bx + x^2 Q(x) \) with \( A, B - 1 \equiv 2^{k+1} \pmod{2^{k+2}} \), \( Q(x) \equiv 0 \pmod{4} \) and expand:
\[
\begin{align*}
f_{2k+1}(x) &= f_{2k}(f_{2k}(x)) \\
&\equiv f_{2k}(A + Bx) \pmod{x^2} \\
&= A + B(A + Bx) + (A + Bx)^2 Q(x) \\
&\equiv A(B + 1) + B^2 x + (A^2 + 2ABx) Q(x) \pmod{x^2} \\
&\equiv 2A + B^2 x \pmod{2^{k+3}} \\
&\equiv 2A + (1 + (B - 1))^2 x \pmod{2^{k+3}} \\
&\equiv 2A + (1 + 2(B - 1))x \pmod{2^{k+3}}.
\end{align*}
\]
This completes the induction. In the same notation,
\[
b_{2k+1} - 2b_{2k} = f_{2k+1}(0) - 2f_{2k}(0) = f_{2k}(A) - 2A = A + BA + A^2 Q(A) - 2A = (B - 1)A + A^2 Q(A) \equiv 2^{k+2} \pmod{2^{k+3}}.
\]