Japan competition problems, 2007

Let $f(n)$ be the number of ways to write $n$ as sum of nonnegative powers of $3$ and $f(0) = 1$.
We can write $n$ as sum of nonnegative powers of $3$ with $k$ $1$s iff $n-k$ is divisible by $3$. Let $n-k = 3m$, then the number of ways to write $n$ as sum of nonnegative powers of $3$ with $k$ $1$s is equal to write $3m$ as sum of positive powers of $3$, and that is equal to $f(m)$. So we get
$$f(n) = \sum_{0 \le m \le n/3} f(m).$$
We can compute $f(100)$ by this relation. First we get $f(100) = f(0) + f(1) + \cdots + f(33)$. And from $f(0) = f(1) = f(2), f(3) = f(4) = f(5) = f(0) + f(1), \cdots, f(30) = f(31) = f(32) = f(0) + \cdots + f(10), f(33) = f(0) + \cdots + f(11)$, we get $f(100) = 34f(0) + 31f(1) + \cdots + 4f(10) + f(11)$. Applying the relation one more time we get
$$\begin{aligned} f(100) &= (34 + 31 + 28)f(0) + (25 + 22 + 19)(f(0) + f(1)) \\ &\quad + (16 + 13 + 10)(f(0) + f(1) + f(2)) \\ &\quad + (7 + 4 + 1)(f(0) + f(1) + f(2) + f(3)) \\ &= 210f(0) + 117f(1) + 51f(2) + 12f(3). \end{aligned}$$
From $f(0) = f(1) = f(2) = 1$ and $f(3) = 2$, we get $f(100) = 402$.