# Powers of 2 in the product of the Fibonacci numbers

I'm working on finding a summation that pulls the powers of 2 out of the product of the Fibonacci numbers.

I've noticed some patterns for the Fibonacci number. For example. Looking at the Fibonacci numbers $${1,1,2,3,5,8,13,21,34,....}$$ You notice that the pattern for powers of 2 is $$0,0,1,0,0,3,0,0,1,0,0,4,0,0,1,0,0,3,....$$ So it is a kind of a recurring pattern but it's copying and pasting on itself.

So I've tried to break it up into pieces. To label every where we see a power of 2 and what power those 2 are. Such as:

$2^1: 3+6n$, $2^3: 6 +12n$, $2^4: 12 +24n$, $2^k: 3k+2kn$

But I can't seem to find a useable summation. To make sure I've made my point clear I'm trying to find an equation that does the same thing as this equation does for $n!$ I just want my summation to work on the product of the Fibonacci numbers. $$\sum_{k=1}^n\left\lfloor{\frac n{2^k}}\right\rfloor$$

• So let me see if I understand you correctly. You want the 2-adic valuation of the product of the first $n$ Fibonacci numbers, in terms of $n$? – user118228 Sep 23 '14 at 23:42
• Yes! That's exactly it! – Fmonkey2001 Sep 23 '14 at 23:59

If $$n$$ is not divisible by $$3$$, we have $$\nu_2 (F_n) = 0$$. Otherwise, if $$n$$ is odd, then $$\nu_2 (F_n) = 1$$. If $$n$$ is even, then $$\nu_2 (F_n) = 2 + \nu_2 (n)$$. There are elementary proofs of this, but it can be seen directly from properties of the $$2$$-adic exponential.

Using this, we can calculate $$\nu_2 (F_1 F_2 \cdots F_{3m}) = \nu_2 (F_1 F_2 \cdots F_{3m+1}) = \nu_2 (F_1 F_2 \cdots F_{3m+2}) =$$ $$\nu_2 (F_3 F_6 \cdots F_{3m}) = \nu_2 (m!) + m + \lfloor \frac{m}{2} \rfloor$$.

So our final formula becomes:

$$\nu_2 (F_1 F_2 \cdots F_n) =\left\lfloor \frac{n}{6} \right\rfloor + \sum_{k=0}^\infty \left\lfloor \frac{n}{3\cdot 2^k} \right\rfloor$$

(The $$\lfloor \frac{n}{6}\rfloor$$ term, which does not have a counterpart in the formulas below, reflects the fact that the $$2$$-adic exponential fails to converge on $$2\mathbb{Z}_2$$.)

Note that the $$p$$-adic valuation has an even simpler pattern when $$p\neq 2$$, though nothing beats $$p=5$$, as we have $$\nu_5 (F_n) = \nu_5 (n)$$, an amusing but surprisingly deep fact. That formula gives us, of course:

$$\nu_5 (F_1 F_2 \cdots F_n) =\sum_{k=1}^\infty \left\lfloor \frac{n}{5^k} \right\rfloor$$

In general, we have the following formula for $$p$$ odd, where $$l$$ denotes the smallest positive integer with $$p \mid F_l$$:

$$\nu_p (F_1 F_2 \cdots F_n) = \left\lfloor \frac{n}{l} \right\rfloor \cdot \nu_p (F_l) + \sum_{k=1}^\infty \left\lfloor \frac{n}{l\cdot p^k} \right\rfloor$$

That last formula is simpler than it looks: there are no known primes for which $$\nu_p (F_l)\neq 1$$, though the leading conjecture is that there are infinitely many; these are called Wall-Sun-Sun primes.

For an encore:

$$\nu_3 (F_1 F_2 \cdots F_n) =\sum_{k=0}^\infty \left\lfloor \frac{n}{4\cdot 3^k} \right\rfloor$$

$$\nu_7 (F_1 F_2 \cdots F_n) =\sum_{k=0}^\infty \left\lfloor \frac{n}{8\cdot 7^k} \right\rfloor$$

$$\nu_{13} (F_1 F_2 \cdots F_n) =\sum_{k=0}^\infty \left\lfloor \frac{n}{7\cdot 13^k} \right\rfloor$$

...and so on.

• Can you help understand one thing? Using the above formula for $n=3$ $$v_2(F_1F_2F_3)=v_2(3!)+3+\lfloor{\frac 32}\rfloor$$ which gives you $$1\neq1+3+1$$. Which isn't right. So what have I done wrong? – Fmonkey2001 Sep 24 '14 at 2:36
• @Fmonkey2001 Using the above formula for $n=1$, $\nu(F_1 F_2 F_3) = \nu_2(1!) + 1 + \lfloor \frac{1}{2} \rfloor = 1$. – Slade Sep 24 '14 at 2:57
• @Fmonkey2001 Okay, I've added a formula that might appeal to you. – Slade Sep 24 '14 at 3:45