Tagged Questions
1
vote
1answer
45 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 ...
2
votes
2answers
49 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
1answer
91 views
recurrence and fibonacci
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
439 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
74 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
547 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
231 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
146 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
136 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
474 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
186 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 ...
10
votes
1answer
242 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 = ...
0
votes
1answer
102 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 ...
27
votes
2answers
396 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 ...
11
votes
2answers
245 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
593 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
220 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
92 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
340 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
195 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?
3
votes
1answer
366 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 ...
-4
votes
1answer
1k 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
978 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 ...
6
votes
3answers
812 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
209 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
745 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 ...
