Question

Let $f_1(x) = x^2 + 4x + 2$ and for $n\ge 2$.Let $f_n(x)$ be the n-fold composition of the polynomial with itself. For example $f_2(x)=f_1(f_1(x))=x^4+8x^3+24x^2+32x+14$ and $S_n$ be the sum of the coefficients of the terms of even degree in $f_n(x)$. For example $S_2=1+24+14=39$. Then identify correct options.

• A. S2025 is divisible by 2
• B. S2025 is divisible by 3
• C. S2024 is divisible by 5
• D. S2024 is divisible by 3

Answer 1

Answer: (B), (D)

S2025 is divisible by 3, S2024 is divisible by 3

Answer 2

Let $f_1(x) = x^2 + 4x + 2$. Let $f_n(x) = f_1(f_{n-1}(x))$ for $n \ge 2$. Let $f_n(x) = a_m x^m + a_{m-1} x^{m-1} + \dots + a_1 x + a_0$. $S_n$ is the sum of the coefficients of the terms of even degree in $f_n(x)$. $S_n = a_0 + a_2 + a_4 + \dots$.

We know that for any polynomial $P(x)$, the sum of coefficients of even degree terms is $\frac{P(1) + P(-1)}{2}$. Applying this to $f_n(x)$, we have $S_n = \frac{f_n(1) + f_n(-1)}{2}$.

Let $a_n = f_n(1)$ and $b_n = f_n(-1)$. $a_1 = f_1(1) = 1^2 + 4(1) + 2 = 7$. $b_1 = f_1(-1) = (-1)^2 + 4(-1) + 2 = 1 - 4 + 2 = -1$.

For $n \ge 2$, $a_n = f_n(1) = f_1(f_{n-1}(1)) = f_1(a_{n-1}) = a_{n-1}^2 + 4a_{n-1} + 2$. For $n \ge 2$, $b_n = f_n(-1) = f_1(f_{n-1}(-1)) = f_1(b_{n-1}) = b_{n-1}^2 + 4b_{n-1} + 2$.

Let's compute the first few terms of the sequence $b_n$: $b_1 = -1$. $b_2 = b_1^2 + 4b_1 + 2 = (-1)^2 + 4(-1) + 2 = 1 - 4 + 2 = -1$. $b_3 = b_2^2 + 4b_2 + 2 = (-1)^2 + 4(-1) + 2 = 1 - 4 + 2 = -1$. By induction, if $b_{k-1} = -1$, then $b_k = f_1(-1) = -1$. Since $b_1 = -1$, $b_n = -1$ for all $n \ge 1$.

Now let's analyze the recurrence for $a_n$: $a_n = a_{n-1}^2 + 4a_{n-1} + 2$. We can rewrite this as $a_n + 2 = a_{n-1}^2 + 4a_{n-1} + 4 = (a_{n-1} + 2)^2$. Let $c_n = a_n + 2$. $c_1 = a_1 + 2 = 7 + 2 = 9$. $c_n = c_{n-1}^2$. $c_1 = 9 = 3^2$. $c_2 = c_1^2 = (3^2)^2 = 3^4$. $c_3 = c_2^2 = (3^4)^2 = 3^8$. In general, $c_n = c_1^{2^{n-1}} = (3^2)^{2^{n-1}} = 3^{2 \cdot 2^{n-1}} = 3^{2^n}$. So, $a_n + 2 = 3^{2^n}$, which means $a_n = 3^{2^n} - 2$.

Now we can express $S_n$ using the formula $S_n = \frac{a_n + b_n}{2}$: $S_n = \frac{(3^{2^n} - 2) + (-1)}{2} = \frac{3^{2^n} - 3}{2}$.

We need to check the divisibility of $S_{2024}$ and $S_{2025}$. $S_{2024} = \frac{3^{2^{2024}} - 3}{2}$. $S_{2025} = \frac{3^{2^{2025}} - 3}{2}$.

• Divisibility of $S_{2025}$ by 2:

  $S_{2025} = \frac{3^{2^{2025}} - 3}{2}$. For $S_{2025}$ to be divisible by 2, the numerator $3^{2^{2025}} - 3$ must be divisible by 4. Since $2^{2025}$ is even, $3^{2^{2025}} \equiv 1 \pmod{4}$. So, $3^{2^{2025}} - 3 \equiv 1 - 3 \equiv -2 \equiv 2 \pmod{4}$. Since $3^{2^{2025}} - 3 \equiv 2 \pmod{4}$, it is of the form $4q + 2$. $S_{2025} = \frac{4q + 2}{2} = 2q + 1$. This is an odd number. An odd number is not divisible by 2.

• Divisibility of $S_{2025}$ by 3:

  $S_{2025} = \frac{3^{2^{2025}} - 3}{2} = \frac{3(3^{2^{2025}-1} - 1)}{2}$. The term $3^{2^{2025}-1}$ is an integer power of 3, so it is an odd number. $3^{2^{2025}-1} - 1$ is an odd number minus 1, which is an even number. Let $3^{2^{2025}-1} - 1 = 2m$ for some integer $m$. $S_{2025} = \frac{3(2m)}{2} = 3m$. This shows that $S_{2025}$ is divisible by 3.

• Divisibility of $S_{2024}$ by 5:

  $S_{2024} = \frac{3^{2^{2024}} - 3}{2}$. For $S_{2024}$ to be divisible by 5, $3^{2^{2024}} - 3$ must be divisible by 10. This means $3^{2^{2024}} - 3 \equiv 0 \pmod{10}$, or $3^{2^{2024}} \equiv 3 \pmod{10}$. The cycle length of powers of 3 modulo 10 is 4. Since $2^{2024}$ is divisible by 4, $3^{2^{2024}} \equiv 1 \pmod{10}$. We need $3^{2^{2024}} \equiv 3 \pmod{10}$. $1 \equiv 3 \pmod{10}$ is false. So, $3^{2^{2024}} - 3$ is not divisible by 10. $S_{2024} \equiv 4 \pmod{5}$, so $S_{2024}$ is not divisible by 5.

• Divisibility of $S_{2024}$ by 3:

  $S_{2024} = \frac{3^{2^{2024}} - 3}{2} = \frac{3(3^{2^{2024}-1} - 1)}{2}$. The term $3^{2^{2024}-1}$ is an integer power of 3, so it is an odd number. $3^{2^{2024}-1} - 1$ is an odd number minus 1, which is an even number. Let $3^{2^{2024}-1} - 1 = 2k$ for some integer $k$. $S_{2024} = \frac{3(2k)}{2} = 3k$. This shows that $S_{2024}$ is divisible by 3.