An IOQM 2023 Problem

image containing math problem statement
A problem from the IOQM 2023 based on recurrence.
Problem contributed by debosmita1729
-----------book page break-----------
Let $f(n)$ be the number of ways to form the sum $n$ using denominations $2^k$ with coefficients $c_k$, therefore:
$n = \displaystyle \sum c_k \cdot 2^k$ where $c_k \in \{0, 1, 2\}$

Let us check the relationship for odd and even $n$.

Let $n$ be odd, and $n = 2k + 1$
$2k + 1 = c_0 + 2c_1 + 4c_2... $

For the right side to be odd, $c_0$ must be $1$, therefore:
$2k  + 1 = 1 + 2c_1 + 4c_2... $
$\Rightarrow 2k  = 2c_1 + 4c_2 + 8c_3...$
$\Rightarrow k = c_1 + 2c_2 + 4c_3...$

We can see that the right side is the expression for $k$. Therefore, 
$f(2k+1) = f(k)$

Therefore, $f(2k + 1) = f(k)$

Similarly, for even $n$, if $n = 2k$, then:

$2k = c_0 + 2c_1 + 4c_2... $
For the right side to be even, $c_0 = 0$ or $c_0 = 2$

-----------book page break-----------
If $c_0 = 0$, then:
$2k = 2c_1 + 4c_2 + 8c_3 ...$
$\Rightarrow k = c_1 + 2c_2 + 4c_3$

Or, if $c_0 = 2$, then:
$2k = 2 + 2c_1 + 4c_2 + 8c_3 ...$
$\Rightarrow k = 1 + c_1 + 2c_2 + 4c_3...$
$\Rightarrow k - 1= c_1 + 2c_2 + 4c_3...$

Therefore, $f(2k) = f(k) + f(k-1)$

For the initial values, we know that there is only one way to make change for $1$ Ben, and $1$ way to make change for $0$ Ben,
$f(0) = 1$ and $f(1) = 1$.

Using the recurrence relations, we break down $f(100)$:
$f(100) = f(50) + f(49)$

Since $49$ is odd, $f(49) = f(24)$. Thus:
$f(100) = f(50) + f(24)$

Next, we expand $f(50)$:
$f(50) = f(25) + f(24)$

Substituting this back into the equation for $f(100)$:
$f(100) = f(25) + 2f(24)$


-----------book page break-----------
Similarly,
$ f(25) = f(12) $, and $f(24) = f(12) + f(11)$
$\therefore f(100) = f(12) + 2(f(12) + f(11)) = 3f(12) + 2f(11)$

Expanding $f(12)$ and $f(11)$ we get:
$f(12) = f(6) + f(5)$ and $f(11) = f(5)$
$\therefore f(100) = 3f(12) + 2f(11) = 3f(6) + 3f(5) + 2f(5) = 3f(6) + 5f(5)$

Expanding $f(6)$ and $f(5)$, gives us:
$f(6) = f(3) + f(2)$ and $f(5) = f(2)$
$\therefore f(100) = 3(f(3) + f(2)) + 5(f(2)) = 3f(3) + 8f(2)$

Expanding $f(3)$ and $f(2)$, we get:
$f(3) = f(1)$ and $f(2) = f(1) + f(0)$
$\therefore f(100) = 3f(1) + 8(f(1)  + f(0)) = 11f(1) + 8f(0)$

Since $f(1) = 1$ and $f(0) = 1$, we get:
$f(100) = 11f(1) + 8f(0) = 11 + 8 = 19$