2
$\begingroup$

I have new Fibonacci number That I want to know is there any special direct formula to count $f(n)$.
Like the normal Fibonacci:
$F(0) = 7$,
$F(1) = 11$,
$F(n) = F(n-1) + F(n-2)$ (n>=2)
For example I want to calculate $f(100)$ without knowing $f(99)$ or $f(98)$.

$\endgroup$
1
  • $\begingroup$ There is. I don't want to go looking for it right now, however. $\endgroup$ Jan 11 '14 at 9:35
3
$\begingroup$

Let $\mathcal{F}(x)$ be the ordinary generating function for the new Fibonacci number: $$\mathcal{F}(x)=\sum_{n\geq 1}F_n x^n$$ Note that \begin{align*} \mathcal{F}(x) = 7x+ 11x^2+ &18x^3+29x^4+47x^5+\cdots\\ x\cdot \mathcal{F}(x) =~~~~~~~~~~~ 7x^2+&11x^3+18x^4+29x^5+47x^6+\cdots\\ x^2\cdot \mathcal{F}(x) =~~~~~~~~~~~~~~~~~~~~~ &7x^3+11x^4+18x^5+29x^6+47x^7+\cdots \end{align*} Then $$(1-x-x^2)\mathcal{F}(x)=7x+4x^2$$ So, $$\mathcal{F}(x)=\frac{7x+4x^2}{1-x-x^2}=7\mathcal{F}_0(x)+4x\mathcal{F}_0(x)$$ where $\mathcal{F}_0(x)$ is the ordinary generating function for the standard Fibonacci numbers, i.e., $\mathcal{F}_0(x)=\sum_{n\geq 1}F^*_{n}x^n$ in which $F^*_n$ is the given by the well-known Binet's formula: $$F^*_n=\frac{(r)^n-(r')^n}{2^n\sqrt{5}}$$ where $r=1+\sqrt{5}$ and $r'=1-\sqrt{5}$

Now we are ready to express the coefficient of $x^n$ in $\mathcal{F}(x)$: $$F_n=7F^*_n+4F^*_{n-1}=7\frac{(r)^n-(r')^n}{2^n\sqrt{5}}+4\frac{(r)^{n-1}-(r')^{n-1}}{2^{n-1}\sqrt{5}}$$

$\endgroup$
7
$\begingroup$

Since $(7,11) = (7,7)+(0,4)$, your sequence is $F(n)=4 Fibonacci(n) + 7 Fibonacci(n+1)$.

$\endgroup$
2
$\begingroup$

The usual method to solve this is :

$$f_{n+2}=f_{n+1}+f_{n}$$

Is

  1. Find the solutions of $X^2=X+1$. This are the roots $r_1$ and $r_2$ of the polynomial $X^2-X-1$. Hence $r_i=\frac{1\pm\sqrt{5}}{2}$
  2. As there are two distinct roots, then $$f_n=A.r_1^n+B.r_2^n$$
  3. Find $A$ and $B$ with the initial values of $f_n$. $$f_0=7=A+B$$ $$f_1=11=A.r_1+B.r_2$$ So $A=\frac{11-7.r_2}{r_1-r_2}$ and $B=\frac{11-7r_1}{r_2-r_1}$
$\endgroup$
0
$\begingroup$

In general, for $\{f_n\} (n=0,1,\cdots)$ such that $f_{n}=f_{n-1}+f_{n-2}\ \ (n\ge 2)$, we have $$f_n=\frac{(\beta^n-\alpha^n)f_1-(\alpha\beta^n-\alpha^n\beta)f_0}{\beta-\alpha}$$ where $$\alpha=\frac{1-\sqrt 5}{2},\beta=\frac{1+\sqrt 5}{2}.$$

So, you can use this as $$f_{100}=\frac{(\beta^{100}-\alpha^{100})\times 11-(\alpha\beta^{100}-\alpha^{100}\beta)\times 7}{\beta-\alpha}$$

$\endgroup$

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.