1
vote
1answer
75 views

General formula of Fibonacci look alike series

I'm trying to discover the general formula of a series defined with recursion: $$ a_1 = 2, a_2 = 3, a_3 = 4 $$ and $$ a_n = a_{n-1} + a_{n-3} $$ It looks like Fibonacci, but the starting points are ...
0
votes
1answer
34 views

Initial values appear from nothing

This answer says that any casual sequence of the kind $y_n = y_{n-1} + y_{n-2} + y_{n-3} + \ldots $ will stay constant-0 because $y_0$ is a sum of zeroes, so is $y_1$ and the rest of the sequence. I ...
3
votes
2answers
89 views

Fibonaaci Recurrence

This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities Given Data in question ...
13
votes
4answers
352 views

Converting recursive equations into matrices

How do we convert recursive equations into matrix forms? For instance, consider this recursive equation(Fibonacci Series): $$F_n = F_{n-1} + F_{n-2}$$ And it comes out to be that the following that ...
1
vote
1answer
68 views

Fibonacci numbers $F_{n+3} + F_{n} = 2F_{n+2}$

Prove $F_{n+3} + F_{n} = 2F_{n+2}$ for any positive integer n. So What I did was this: fn+ fn+1 = fn+2 fn + fn+1 = fn+2 => fn+2 -fn+1 fn+1 + fn+2 = fn+3 then I subsituted into equation in ...
1
vote
2answers
93 views

How many $a$-nary sequences of length $b$ never have $c$ consecutive occurrences of a digit?

Let $S(a,b,c): = \#\{a$-nary sequences of length $b$ without $c$ consecutive occurrences of a digit$\}$. For example, $S(2,n,3)$ would be the number of binary sequences of length $n$ without $3$ ...
1
vote
4answers
46 views

Help understanding Recursive algorithm question

We have a function that is defined recursively by $f(0)=f_0$, $f(1)=f_1$ and $f(n+2) = f(n)+f(n+1)$ for $n\geq0$ For $n\geq0$, let $c(n)$ be the total number of additions for calculating $f(n)$ ...
3
votes
2answers
87 views

a manipulation of Fibonacci recurrence

Let $F_n$ be the Fibonacci number, and we know $F_{n+2} = F_{n+1} + F_{n} $ with $F_0 =1,F_1 = 1$ And this can be manipulated to $F_{n+6} = 4F_{n+3} + F_n$ if we let n be a multiple of 3, we can ...
-1
votes
2answers
125 views

how to find nth term of different fibonacci series with golden ratio [duplicate]

what i know : if i want to find $Nth$ term of a fibonacci series like : 1 1 2 3 5 8 13 21 ....... then to find $6th$ term we use golden ratio ...
1
vote
3answers
88 views

How to go about solving this recurrence relation?

In my discrete math class we were given the problem of finding an explicit formula for this recurrence relation and proving its correctness via induction. $$a_n=2a_{n-1}+a_{n-2}+1, a_1 = 1, a_2=1.$$ I ...
3
votes
1answer
128 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
2
votes
2answers
105 views

Internet problem solving contest question

I am trying to solve a problem from the IPSC http://ipsc.ksp.sk/2001/real/problems/f.html It basically asks to compute the following recursion. ...
1
vote
3answers
80 views

recurrence relation for squares of fibonacci numbers

I have a problem finding a proof that the squares of the Fibonacci numbers satisfy the recurrence relation $a_{n+3} - 2*a_{n+2} - 2*a_{n+1} + a_n = 0$ and solving this recurrence relation. Some help ...
1
vote
1answer
89 views

Matrix powers and recurrence relations

The nth Fibonacci number can be found by raising the matrix $\begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix}$ to the nth power. Are there other recurrence formulas that can be solved like this? ...
1
vote
4answers
2k views

how to find nth term in a fibonacci series or sum of a series of fibonacci numbers

A series is given as $1,6,7,13,20,33,.......$ and so on Find the sum of first 52 terms? what i know is The sum of the first n Fibonacci numbers is the [(n + 2)nd Fibonacci number - 1] . So the sum ...
0
votes
3answers
221 views

Prove the Number of Additions of Fibonacci Number Algorithm

I am studying for a final exam and I'm having trouble with this question: The following recursive algorithm FIB takes as input an integer $n \ge 0$ and returns the $n$-th Fibonacci number $F_n$: ...
3
votes
2answers
575 views

Inductive proof of the closed formula for the Fibonacci sequence [duplicate]

Fibonacci numbers $f(n)$ are defined recursively: $f(n) = f(n-1) +f(n-2)$ for $n > 2$ and $f(1) = 1$, $f(2) = 1$. They also admit a simple closed form: $$\sqrt 5 f( n ) = \left(\dfrac{1+ \sqrt ...
3
votes
1answer
70 views

A Generalized Fibonacci sequence

I have the following recurrence $$u_{n+1}=u_{n}+a^{N-n}u_{n-1}\quad n\ge 1$$ where $$N\ge 1,\quad u_1=u_0=1,\quad 0< a\le 1$$ I want to find out $u_N$. My Try: For $a=1$ this is just the Fibonacci ...
0
votes
3answers
84 views

Fiddling with a Fibonacci-Like Sequence

Let $X\in\mathbb{Z}.$ Let $F_n$ be a sequence of positive integers given by $$F_{i+1}=F_i+F_{i-1}$$ $$F_2=X*F_1+F_0$$ I am trying to find an upper bound or (sharp) inequality of $F_i$ in terms of ...
1
vote
1answer
134 views

Register Machine on Fibonacci Numbers

This problem is easy to understand but I am struggling to come up with any solutions. According to Wikipedia a register machine is a generic class of abstract machines used in a manner similar to a ...
3
votes
3answers
137 views

“Fat” sets of integers and Fibonacci numbers

Let us call a set of integers "fat" if each of its elements is at least as large as its cardinality. For example, the set $\{10,4,5\}$ is fat, $\{1,562,13,2\}$ is not. Define $f(n)$ to count the ...
1
vote
2answers
99 views

What is the asymptotical bound of this recurrence relation?

I have the recurrence relation, with two initial conditions $$T(n) = T(n-1) + T(n-2) + O(1)$$ $$T(0) = 1, \qquad T(1) = 1$$ With the help of Wolfram Alpha, I managed to get the result of ...
0
votes
1answer
181 views

recurrence and fibonacci [closed]

could someone possibly help me with a proof. prove $a_n = F_{2n-1}$ for fibonacci numbers and a recurrence relation where $a_1 = 1$ $a_2 = 2$ $a_3 = 5$ $a_4 = 13$ $a_5 = 34$ 89,233,610,1597 ...
2
votes
1answer
622 views

Recurrence relation, Fibonacci numbers

$(a)$ Consider the recurrence relation $a_{n+2}a_n = a^2 _{n+1} + 2$ with $a_1 = a_2 = 1$. $(i)$ Assume that all $a_n$ are integers. Prove that they are all odd and the integers $a_n$ and $a_{n+1}$ ...
1
vote
1answer
111 views

Power Variant of Fibonacci sequence

I was trying to simplify the following sequence, such that I can calculate the $n$th term in $\log n$ time. This can be done, if we can express the $n$th in terms of combinations of Fibonacci like ...
0
votes
1answer
1k views

How to solve tribonacci series [duplicate]

Possible Duplicate: Fibonacci, tribonacci and other similar sequences Suppose my Tribonacci series is like this: \begin{equation} T(n) = T(n-1) + T(n-2) +T(n-3) \end{equation} with initial ...
4
votes
1answer
294 views

Summation Of Product Of Fibonacci Numbers

Im trying to find out a general term for the following summation of products of fibonacci numbers:-- $$\sum_{k=4}^{n+1} F_{k}F_{n+5-k}\; , n \geq 3$$ I tried using Binet's equation but I am ...
1
vote
2answers
252 views

Fibonacci Sequence Variants

I learnt about finding the $n$th Fibonacci number using matrix exponentiation in $\log n$ time. Then I tried finding similar formula for sequences of the form $$S_{n} = S_{n-1} + S_{n-2} + a n + b$$ ...
0
votes
1answer
232 views

Fibonacci sequence, strings without 00, and binomial coefficient sums

Refer to the sequence $S$ where $S_n$ denotes the number of n-bit strings that do not contain the pattern 00. By considering the number of n-bit strings with exactly i 0's, show that $\displaystyle ...
4
votes
4answers
1k views

Closed form solution of Fibonacci-like sequence

Could someone please tell me the closed form solution of the equation below. $$F(n) = 2F(n-1) + 2F(n-2)$$ $$F(1) = 1$$ $$F(2) = 3$$ Is there any way it can be easily deduced if the closed form ...
6
votes
1answer
239 views

Finding ($2012$th term of the sequence) $\pmod {2012}$

Let $a_n$ be a sequence given by formula: $a_1=1\\a_2=2012\\a_{n+2}=a_{n+1}+a_{n}$ find the value: $a_{2012}\pmod{2012}$ So, in fact, we have to find the value of ...
11
votes
1answer
296 views

Why do the Fibonacci numbers recycle these formulas?

The Fibonacci numbers $F_n = 0, 1, 1, 2, 3, 5, 8, 13, \dots$ obey the following recurrence relations, $ \begin{aligned} &F_{n}-\;F_{n-1}-F_{n-2} = 0\\[1.5mm] &F_{n-1}^3-F_{n}^3-F_{n+1}^3 = ...
1
vote
1answer
126 views

“Non-commutative” Recurrence relation $ C_m = \alpha_m C_{m-1} + \beta_m C_{m-2} $

I have a problem, which is probably quite trivial. Consider a recurrence relation of the form $$ C_m = \alpha_m C_{m-1} + \beta_m C_{m-2}, $$ where the coefficients $\alpha_m$ and $\beta_m$ are ...
30
votes
3answers
615 views

Very curious properties of ordered partitions relating to Fibonacci numbers

I came across some interesting propositions in some calculations I did and I was wondering if someone would be so kind as to provide some explanations of these phenomenon. We call an ordered ...
12
votes
2answers
295 views

Generalized Fibonacci Sequence Question

The Fibonacci Sequence is defined as the recurrence $a(n)=a_{n-1}+a_{n-2}$ where $a(0)=0$ and $a(1)=1$. Today, I was bored so I considered the sequence $a(n)=\sqrt{a_{n-1}}+\sqrt{a_{n-2}}$. Ten ...
7
votes
8answers
829 views

Need help deriving recurrence relation for even-valued Fibonacci numbers.

That would be every third Fibonacci number, e.g. $0, 2, 8, 34, 144, 610, 2584, 10946,...$ Empirically one can check that: $a(n) = 4a(n-1) + a(n-2)$ where $a(-1) = 2, a(0) = 0$. If $f(n)$ is ...
1
vote
4answers
261 views

Generalized Fibonacci sequences

Why Fibonacci sequence start at $0$, Tribonacci sequence with $0,0$, Tetranacci with $0,0,0$, etc. [ref OEIS] Has any good reasons for that? These sequences arise in generalization of Pascal Triangle ...
1
vote
1answer
101 views

Recovering two first terms from sequence $f(n)=f(n-1)+f(n-2)$

Having very simple sequence $f(n)=f(n-1)+f(n-2)$ and having $n-th$ term given how can we calculate from which first two terms this $n-th$ term came? I know the answer can be not unique so highest ...
2
votes
2answers
600 views

Recurrence for a lagged Fibonacci sequence

I know how to do the matrix for the standard $f(n) = f(n-1) + f(n-2)$ relationship, but what if it's piecewise? For instance, $f(1)$ through $f(30)$ have some preset values, and then for $f(31)$ ...
3
votes
1answer
274 views

Expanding the generating function of the Fibonacci numbers to find a cute formula

$F_0=1$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$. The generating function is $-\frac{1}{x^2+x-1}$. I have to expand it to prove that $F_n=\sum_k\binom{k}{n-k}$. Could you help me please?
4
votes
1answer
543 views

On the generating function of the Fibonacci numbers

Let's define the Fibonacci numbers as $F_0=1$, $F_1=1$ and $F_n=F_{n-1}+F_{n-2}$. Using this recurrence I was able to calculate the generating function of the Fibonacci numbers to be ...
-3
votes
1answer
4k views

Fibonacci recurrence relations

I came a cross this problem in my regular study of Fibonacci series. Please solve this problem. Solve the Fibonacci recurrence relation $F_{n+2} = F_{n+1} + F_n$, given $F_0 = 1 = F_1$. Show that ...
4
votes
2answers
1k views

Fibonacci, tribonacci and other similar sequences

I know the sequence called the Fibonacci sequence; it's defined like: $\begin{align*} F_0&=0\\ F_1&=1\\ F_2&=F_0+F_1\\ &\vdots\\ Fn&=F_{n-1} + F_{n-2}\end{align*}$ And we ...
8
votes
3answers
2k views

Interesting properties of Fibonacci-like sequences?

Everyone is familiar with the Fibonacci Sequence, [0] 1 1 2 3 5 8 ... and many of it's interesting properties. For example, as the sequence continues, the ratio of ...
6
votes
1answer
259 views

Common terms in general Fibonacci sequences

Mathworld notes that "The Fibonacci and Lucas numbers have no common terms except 1 and 3," where the Fibonacci and Lucas numbers are defined by the recurrence relation $a_n=a_{n-1}+a_{n-2}$. For ...
3
votes
2answers
1k views

Deriving formulas for recursive functions

If I had a recursive function (f(n) = f(n-1) + 2*f(n-2) for example), how would I derive a formula to solve this? For example, with the Fibonacci sequence, Binet's ...