4
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – user118228 Sep 23 '14 at 23:42
  • $\begingroup$ Yes! That's exactly it! $\endgroup$ – Fmonkey2001 Sep 23 '14 at 23:59
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Fmonkey2001 Sep 24 '14 at 2:36
  • $\begingroup$ @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$. $\endgroup$ – Slade Sep 24 '14 at 2:57
  • 1
    $\begingroup$ @Fmonkey2001 Okay, I've added a formula that might appeal to you. $\endgroup$ – Slade Sep 24 '14 at 3:45

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.