"Binomiacci" Sum

Calculus Level 3

Let $\{a_0, a_1, a_2 \ldots, a_n\}$ be the set of integers that satisfy $\sum_{k=0}^{n} \binom{n}{k}a_k = F_n\ \ \forall n \in \{1,2,3,4,\ldots \},$ where $F_n$ is the $n^\text{th}$ Fibonacci number $(F_1=1, F_2=1, F_3=2, \ldots, F_{n+1} = F_n + F_{n-1}).$ Then we have $\lim_{n\rightarrow\infty} \frac{a_{n+1}}{a_n} = \frac{a+\sqrt{b}}{c},$ where $a$ , $b$ , and $c$ are integers with $a>0$ and $b$ square-free. What is $a+b+c?$

The answer is 4.

1 solution

Mark Hennings
Feb 9, 2018

Using the Binomial transform and Binet's Formula for the Fibonacci numbers, we have $\begin{aligned} a_n & = \; \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} F_k \; =\; \tfrac{(-1)^n}{\sqrt{5}}\sum_{k=0}^n (-1)^k \binom{n}{k}\left[\left(\tfrac{1+\sqrt{5}}{2}\right)^k - \left(\tfrac{1-\sqrt{5}}{2}\right)^k\right] \\ & = \; \tfrac{(-1)^n}{\sqrt{5}}\left[\left(1 - \tfrac{1+\sqrt{5}}{2}\right)^n - \left(1 - \tfrac{1-\sqrt{5}}{2}\right)^n\right] \; = \; \tfrac{(-1)^n}{\sqrt{5}}\left[\left(\tfrac{1-\sqrt{5}}{2}\right)^n - \left(\tfrac{1 + \sqrt{5}}{2}\right)^n\right] \\ & = \; (-1)^{n+1}F_n \end{aligned}$ and so $\lim_{n \to \infty} \frac{a_{n+1}}{a_n} \; =\; -\tfrac{1+\sqrt{5}}{2}$ so that $a=1$ , $b=5$ , $c=-2$ , and the answer is $\boxed{4}$ .

Why is it -(1+sqrt(5))/2 instead of (1+sqrt(5))/2 In other words, why is it negative?

Michael Wang - 3 years, 3 months ago

Because $a_n = (-1)^{n+1}F_n$ , and so the signs of $a_n$ alternate.

Mark Hennings - 3 years, 3 months ago

Could you provide some detail about the very first step, $a_n=\displaystyle\sum_{k=0}^n (-1)^{n-k} \dbinom{n}{k} F_k \text{?}$ Thanks.

zico quintina - 3 years, 3 months ago

Look up the Binomial Transform on (e.g.) Wikipedia.

Mark Hennings - 3 years, 3 months ago

Ah, OK, thanks; I thought you were just referring to the binomial theorem, didn't realize this was something different.

zico quintina - 3 years, 3 months ago

Isn't there another series (with the corresponding limit probably divergent) beginning with a0=1 that satisfies the original sum?

Chris Clark - 3 years, 3 months ago

The Binomial Transform is an invertible process, so the sequence $a_n$ is obtained from the sequence $F_n$ uniquely.

Mark Hennings - 3 years, 3 months ago

OK, but I take it then that F0 is 0, so the application of the transform presumes that a0=0. My point being there is another series that you can construct with a0=1. It doesn't really matter because it doesn't lead to a solution, but the problem should not imply that there is a unique set of integers that satisfy the original sum.

Chris Clark - 3 years, 3 months ago

@Chris Clark – $F_0$ is certainly $0$ . You are right in that the defining equation in the question should be for $n \ge 0$ , and not just for $n \ge 1$ . It does not affect the answer, however. If we kept the defining equation for $n \ge 1$ only, so that we could choose $a_0$ freely, then the correct defining equation would be $\sum_{k=0}^n \binom{n}{k}a_k \; = \; F_n + a_0\delta_{n0} \hspace{2cm} n \ge 0$ and hence the Binomial Transform would tell us that $a_n \; = \; \sum_{k=0}^n (-1)^{n-k}\binom{n}{k}[F_k + a_0\delta_{k0}] \; = \; (-1)^n[-F_n + a_0] \hspace{2cm} n \ge 0$ and that would still give $\frac{a_{n+1}}{a_n} \; = \; - \frac{F_{n+1} - a_0}{F_n - a_0} \; \to \; -\tfrac{1+\sqrt{5}}{2} \hspace{2cm} n \to \infty$

Mark Hennings - 3 years, 3 months ago

nerrrrrrrrrrd

Lee Isaac - 3 years, 3 months ago

I think the first statment is not rigorous enought. It may say let {a n} be the sequence... if not, you are putting only a finite number of elements in the sequence (n+1) and the sumation is taken only until this number n so that you then can't difine the sequence. Anyway, as it has been pointed out in another comment, a 0 may vary so that you can't say let {a_n} be """the""" sequence...

I don't know if I'm wrong or if someone is undertanding me but I only say that the initial statment was very confusing to me it's because I'm not very used to this kind of problems but...

Pau Cantos - 3 years, 3 months ago

As discussed elsewhere, the problem should really require the identity $\sum_{k=0}^n \binom{n}{k}a_k \; = \; F_n$ to be true for all integers $n \ge 0$ , and not just for $n \ge 1$ . If the formula holds for all $n \ge 0$ , then the sequence $a_n$ is uniquely defined. If the formula only holds for $n \ge1$ , there is a degree of inexactness about the definition of the sequence $a_n$ . The lack of precision does not affect the answer to the question, but it does mean that there is not a single sequence $(a_n)$ with the stated properties.

@Romain Bouchard

Mark Hennings - 3 years, 3 months ago

Let a0 be free variable，then the general term formula will be replaced by an=((-1)^n)(a0-Fn). As you have said, it does not affect the answer when n goes to ∞.

Zhao Yunchao - 3 years, 3 months ago

@Zhao Yunchao – See my comments with Chris Clark, where I derived this formula...

Mark Hennings - 3 years, 3 months ago

@Mark Hennings – Yeah,that's it!

Zhao Yunchao - 3 years, 3 months ago

I found that it was -goldenRatio, = -(1+sqrt(5))/2, but as i'm still a little dumb i choose b = -5... feel so bad to have the answer wrong putting "-4" xD

Arthur Medemblik - 3 years, 3 months ago

So it must be negative 2... Clever!

Roliver Romero - 3 years, 3 months ago

I learned something new today: If you multiply the rows of Pascal's triangle by the alternating Fibonacci sequence the sums are the Fibonacci sequence itself!

Jeremy Galvagni - 3 years, 2 months ago

"Binomiacci" Sum

The answer is 4.

1 solution

0 pending reports