6
$\begingroup$

I have been stuck on this question for a pretty long time. My teacher says that we should find a small pattern, but I can't find one. Can anyone give me a hand?

Let $b_n$ be the number of positive integers whose digits are all $1$, $3$, or $4$, and add up to $n$.

For example, $b_5 = 6$, since there are six integers with the desired property: $41, 14, 311, 131, 113,$ and $11111$.

Prove that $b_n$ is a perfect square if $n$ is even.

$\endgroup$
  • 2
    $\begingroup$ oeis.org/A006498 $\endgroup$ – Belgi Aug 21 '14 at 0:48
  • 1
    $\begingroup$ Looking at a few of the even cases, it looks to be a bit more specific: $b_{2n}=f_n^2$ where $f_n$ is the $n$-th Fibonacci number... $\endgroup$ – Semiclassical Aug 21 '14 at 0:57
3
$\begingroup$

First note that since $F_n=F_{n-1}+F_{n-2}$, we have $$ \begin{align} F_n^2 &=F_{n-1}^2+F_{n-2}^2+2F_{n-1}F_{n-2}\\ &=2F_{n-1}^2+2F_{n-2}^2-(F_{n-1}-F_{n-2})^2\\ &=2F_{n-1}^2+2F_{n-2}^2-F_{n-3}^2\tag{1} \end{align} $$ a recursion for the squares of the Fibonacci numbers.

The generating function for the count of numbers whose digits are $1$, $3$, or $4$, and whose digits sum to $n$ is $$ \frac1{1-x-x^3-x^4}=\sum_{k=0}^\infty\left(x+x^3+x^4\right)^k\tag{2} $$ To examine the coefficients of the even powers of $x$, we compute the even part of $(2)$: $$ \begin{align} \frac12\left(\frac1{1-x-x^3-x^4}+\frac1{1+x+x^3-x^4}\right) &=\frac{1-x^4}{1-x^2-4x^4-x^6+x^8}\\ &=\frac{1-x^2}{1-2x^2-2x^4+x^6}\tag{3} \end{align} $$ Since the denominator of $(3)$ is $1-2x^2-2x^4+x^6$, the coefficients of $x^{2n}$ in $(3)$ satisfy the recursion $a_n=2a_{n-1}+2a_{n-2}-a_{n-3}$, which is recursion $(1)$, satisfied by the squares of the Fibonacci numbers.

Computing the beginning of the Taylor series for $(3)$, we get $$ \frac{1-x^2}{1-2x^2-2x^4+x^6}=1+x^2+4x^4+9x^6+\dots\tag{4} $$ and since the coefficients satisfy $(1)$, they are the squares of the Fibonacci numbers.

$\endgroup$
1
$\begingroup$

A direction (I leave it to you to see where this goes) : We can prove that $$ b_{n}=b_{n-1}+b_{n-3}+b_{n-4} $$

with initial values given by $$ b(1)=1,\, b(2)=1,\, b(3)=2,\, b(4)=4 $$

We can see this is true since we can generate a sequence that adds to $n$ with a sequence that adds to $n-1$ with adding $1$to be the rightmost number in the sequence (and similarly with $b_{n-3},b_{n-4})$, you can convince yourself that this way avoids repetitions in counting.

Since this is a linear recursion we can solve it: Note that $i$ is a root of the characteristic polynomial $$ p(x)=x^{4}-x^{3}-x-1 $$

and thus so is $-i$ and using polynomial division we are left with a quadratic which roots are real and easy to find using the quadratic formula. This should at least give you a formula for $b_{n}$. You can then try to see if setting $b_{2n}$ in the formula you can write it as a square. It might be worth noting that in the expression for $b_{n}$ you will have a sum with $$ a(i)^{n}+b(-i)^{n} $$

where $a,b$ will be known using the initial conditions and $i^{n}=(-i)^{n}=1$ when $n$ is even and so this will reduce to $a+b$.

$\endgroup$
1
$\begingroup$

Hi I have found the pattern, and I hope it helps.

By just listing out the value of $b_n$, $b_2$=1=$1^2$, $b_4$=4=$2^2$, $b_6$=9=$3^2$, $b_8$=25=$5^2$, $b_{10}$=64=$8^2$, $b_{12}$=169=$13^2$, $b_{14}$=441=$21^2$...... We can see that the numbers under the power are Fibonacci numbers.

$\endgroup$
  • $\begingroup$ This is described in the oeis link along with other descriptions (as well as in the other comment) $\endgroup$ – Belgi Aug 21 '14 at 1:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.