2

Given a positive integer $n$, how many ways are there to write it as $a_0+2a_1+4a_2+\dots+2^na_n$ such that $a_i\in\{0,1,2,3\}$ for all $i$?

If the coefficients were allowed to be in just $\{0,1\}$, there would be a unique representation.

But here, for $n=2$ and $n=3$ there are two representations each. For $n=4$ there are three representations: $(a_0,a_1,a_2)=(2,1,0),(0,2,0),(0,0,1)$.

pi66
  • 7,164
  • you can see such numbers representations in additions before carrying over –  Jul 21 '16 at 09:19

1 Answers1

0

There are two choices for $a_0$ because it must have the parity of $n$. Then we can subtract off $a_0$, divide by $2$, and express $(n-a_0)/2$. So if $F(n)$ is the number of ways to express $n$, we have $F(n)=F(\lfloor n/2\rfloor)+F(\lfloor n/2\rfloor-1)$. With the starting values you gave, we find $F(n)=1+\lfloor n/2\rfloor$.

Ross Millikan
  • 374,822