# New Fibonacci sequence

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 count f(100) without knowing f(99) or f(98).

-
There is. I don't want to go looking for it right now, however. –  Jan Dvorak Jan 11 '14 at 9:35

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

-

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

-

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

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

-