Questions regarding functions defined recursively, such as the Fibonacci sequence.

learn more… | top users | synonyms (2)

0
votes
1answer
28 views

Stability of difference equation considering only positive values

I'm analyzing the stability of such system difference equation with the constraint that $y_n \geq 0$ $\forall n \geq 0$ : $y_n = B y_{n-1} + D y_{n-2} \enspace (1)$ Using variable transform, the ...
5
votes
2answers
1k 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 ...
5
votes
1answer
366 views

Deriving a recurrence relation

The number of sequences of length $n$ consisting of positive integers such that the opening and ending elements are $1$ or $2$ and the absolute difference between any $2$ consecutive elements is $0$ ...
1
vote
0answers
65 views

How to solve the recurrence relation $f(n) = 1 - (1 - f(n - 1) \times (1 - p)) ^ 2$ to find a closed-form solution?

A friend of mine gave me a math problem whose answer turned out to be $$f(n) = 1 - (1 - f(n - 1) \times (1 - p)) ^ 2$$ for some fixed $p$. I'm trying to find a closed-form solution to the ...
2
votes
2answers
85 views

A Recurrence Equation From a Game

$a_n=a_{n-1}(a_{n}-a_{n-2}+1)$ The above equation is defined in $[0,m]$ st. $a_{0}=0$ and $a_m=1$. It turned up as I was trying to analyze a simple richman game. I have managed to solve the equation ...
1
vote
2answers
93 views

How to solve $f_{n}(x)=xf_{n-1}(x)-f_{n-2}(x)$?

How to solve the following recurrence relation $$f_{n}(x)=xf_{n-1}(x)-f_{n-2}(x)$$ with the initial conditions $f_{1}(x)=x, f_{2}(x)=x^2-1$? The answer is that ...
0
votes
1answer
111 views

Getting the closed form solution of a third order recurrence relation with constant coefficients

This is part of the proof of finding the closed from solution of third order recurrence relation I know that the closed form will look like the following And this is the part of the proof I can ...
1
vote
2answers
89 views

Can I get a hint on solving this recurrence relation?

I am having trouble solving for a closed form of the following recurrence relation. $$\begin{align*} a_n &= \frac{n}{4} -\frac{1}{2}\sum_{k=1}^{n-1}a_k\\ a_1 &= \frac{1}{4} \end{align*}$$ The ...
0
votes
2answers
637 views

Finding the closed form solution of a third order recurrence relation with constant coefficients [duplicate]

How would you solve for the closed form solution of a(n) given the general form of the third order linear homogenous recurrence relation with real constant coefficients. ...
0
votes
2answers
165 views

Mathematical formula to find adjacent items in a grid

I have a 3x3 grid of dots. Selecting any one of the 9 dots, I need to find out which of the remaining dots are adjacent to the first dot. So, if for example we chose the first dot in the first row ...
0
votes
2answers
86 views

A basic problem on recurrence relation

How to solve this recurrence relation $a_n=(1-p) + (2p-1)a_{n-1}, n \geq 2$ where $a_1= \beta$ and $p$ some arbitrary number.
9
votes
3answers
289 views

The integer $c_n$ in $(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$

For non-negative integer $n$, write $$(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$$ where $a_n,b_n,c_n$ are integers. For any non-negative integer $m$, prove or disprove ...
-5
votes
1answer
73 views

Recursive definitions - cannot figure this one out

I need to find a recursive solution to the below problem. $$a_n=n(n-1)$$ for $n \in \mathbb{N}$ Calculating some values gives \begin{align*} a_1&= 1\cdot (0)=0\\ a_2&= 2\cdot (2-1)=2\\ ...
4
votes
1answer
3k views

Upper bound for $T(n) = T(n - 1) + T(n/2) + n$ with recursion-tree

I'm reading through Introduction to Algorithms, 3rd ed. and I got stuck on the following recurrence (exercise 4.4-5): $$T(n) = T(n - 1) + T(n/2) + n$$ The exercise asks you to find the upper bound ...
0
votes
1answer
161 views

Solving recursive relations using matrix method.

I am looking to solve the recursive relation $P_n=2P_{(n-2)}+3P_{(n-3)}+7P_{(n-7)}$ using the matrix method. The matrix method solves the recursive relation in ...
0
votes
1answer
49 views

Recipe for solving linear discrete-time model for which N(t) is influenced by N(u) and N(v) u<t, v<t.

For solving linear discrete time model of the form $$N_{t+1}=pN_{t}+c$$ (when saying solving I mean that $N_{t}$ is expressed only in function of $p$, $c$ and the initial conditions) one can first ...
1
vote
2answers
63 views

Find the value of the the term

The sequence $a_1,a_2,a_3,\ldots$ satisfies $a_1=1$, $a_2=2$, and $$a_{n+2}=\frac2{a_{n+1}}+a_n\;;$$ find the value of $$\frac{a_{2012}2^{2009}}{2011}$$
0
votes
2answers
157 views

Recurrence relation for words length $n$

I need to solve following question: "An alphabet consists out of 4 letters $a,b,c,d$ and 3 numbers $1,2,3$. Find the recurrence relation for the number of words of length $n$ where no two numbers are ...
1
vote
0answers
51 views

Closed form of an inhomogeneous non-constant recurrence relation

I try to find a closed form for the $f_k$'s (at least for $f_1$) satisfying the following recurrence relation for any fixed $n>0$: $f_0 = 0$, $f_n = 0$, and $f_k = \frac{n}{2k}(f_{k-1} + f_{k+1} + ...
6
votes
2answers
366 views

How to prove $\lim_{n\to\infty}\frac{\log_{2}{(f_{n})}}{(\log_{2}{n})^2}=\frac{1}{2}$?

For any $n\in N$, such $f_{1}=1$, and such $$f_{2n+1}=f_{2n}=f_{2n-1}+f_{n},$$ prove that $$\lim_{n\to\infty}\dfrac{\log_{2}{(f_{n})}}{(\log_{2}{n})^2}=\dfrac{1}{2}.$$
2
votes
0answers
103 views

Showing the relationship between Lucas and Fibonacci numbers with a recursive relationship

Given the equation $$L_{n+k}-(-1)^kL_{n-k}=5F_kF_n$$ Where $\{L\}$ is the set of Lucas numbers and $\{F\}$ is a Fibonacci sequence, $n$ and $k$ are both $>0$ and integers, how would one develop ...
5
votes
2answers
169 views

Solving a recurrence for a probability?

I came across the following recurrence relation when exploring properties of a certain type of randomized perfect binary tree: $$ T(0) = \frac{1}{2} $$ $$ T(k + 1) = 1 - T(k)^2 $$ (Specifically, ...
3
votes
3answers
89 views

General solution to a Growth equation

I'd like to compute a formula that describes a population growth. The population starts with $N(t=0)$ individuals. At each time step there are births and deaths. The number of births at time $t$ is ...
5
votes
3answers
315 views

Find inverse for the closed-form expression of linear recurrence relation

I am trying to find an inverse of the following formula: $$ a_n=\frac{2+\sqrt{6}}{4}(1+\sqrt{6})^n+\frac{2-\sqrt{6}}{4}(1-\sqrt{6})^n $$ This formula is a closed-form expression of a linear ...
1
vote
1answer
2k views

Difference equations and Matlab (some working)

The difference equations below model the yearly populations of wolves and moose, measured in hundreds. The wolves kill the moose for food. http://imgur.com/jV3v06Y I think I've worked out what x and ...
1
vote
1answer
74 views

Is this recursion well-defined?

I have a recursion defined by $$ f(n)=\max\{0,-c+pf(n-1)+(1-p)f(n+1)\} $$ with $0.5<p \leq 1$ and $f(0)=R>0$ and $f(m)=0$ for some $m>0$. I am trying to show that $f(n)$ is decreasing in ...
0
votes
4answers
271 views

How do I derive a characteristic equation for this specific recurrence relation?

I have no problems solving recurrence relations with two roots, but I've just encountered one with one root: $c_{n+1} = 3c_{n}+1$ such that $c_{0} = 0$. In my solving process, I suppose I've gotten ...
0
votes
2answers
33 views

Recurrence relations for $a_{n+2}$

I'm trying to figure out how to find closed form equations for recurrence relations. I can find lots of examples for solving equations such as $a_{n} = ca_{n-1} + ca_{n-2}$ and $a_{n+1} = ca_{n} + ...
2
votes
0answers
71 views

How prove this sequences have limts and find this value?

let $f:R\longrightarrow R$,and $f(x)=x-\dfrac{x^2}{2}$,and $$L_{1}(x)=f(x),L_{2}(x)=f(f(x)),L_{3}(x)=f(L_{2}(x)),\cdots,L_{n}(x)=f(L_{n-1}(x))$$ and let $$a_{n}=L_{n}\left(\dfrac{17}{n}\right)$$ ...
0
votes
1answer
67 views

How to compute the formula of $S_n$

$S_1$=a, $S_2$=b, $S_n$=|$S_{n-1}$-$S_{n-2}$|(n $\ge$3). Can I compute the formula of $S_n$? Thanks in advance.
1
vote
1answer
98 views

Recurrence relation with unequal division

$$T(n) = T(3n/4) + T(n/3) + n$$ Please help me solve this recurrence relation. Somehow even Akra_Bazzi method doesn't seem to work in this case
1
vote
0answers
66 views

looking for explanation behind solution for a 1st order recurrence relation.

In lecture, we covered 1st order recurrence relations and came up with a solution by inspection. I sort of see that we're finding the next term in the sequence by multiplying the initial condition by ...
0
votes
0answers
91 views

Continued fraction of $\gamma+1$ using recursion

Number $\gamma,$ the Euler-Mascheroni constant, is defined as the value of $$\gamma = \lim_{n\to\infty} \sum_{k=1}^n \frac{1}{k} - \ln(n).$$ We know that $$\lim_{n\to\infty} ...
3
votes
2answers
672 views

Solving for the closed term solution of a third order recurrence relation with real constant coefficients

How would you solve for the closed term form of $a(n)$ given the general form of the third order linear homogenous recurrence relation with real constant coefficients. ...
2
votes
2answers
239 views

recurrence relation homework question

This is a homework question let $a_n$ number of n digit quaternary $(0,1,2,3)$ sequences in which there is never a$ 0 $anywhere to the right of a $3$. Solve for $a_n$ bot sure how to go about this. ...
4
votes
2answers
79 views

Recurrence Relation Homework Question 3

This is a HW question Consider the set $T={A,B,C,1,2,3,4}$. For $ n\geq 0$ let $c_n$ be the number of n-character sequences of elements of T that contain no consecutive letters (distinct or ...
1
vote
1answer
330 views

Solving Recurrences Using Annihilators

I've recently learnt how to use "annihilators" to find closed form solutions to recurrence relations. For instance, if I have the recurrence: $$\begin{align} f(0) &= 10 \\ f(n) &= 4 \, f(n-1), ...
3
votes
3answers
53 views

Recurrence Relation Homework question 2

This is a HW question. Find a recurrence relation for $b_n, n \geq 0 $where $b_n$ is the number of ways to partition $s= {1,2,3,...n}$ into exactly 2 subsets. I am looking for a hint on how to go ...
0
votes
1answer
140 views

probability of sum of a given set of whole numbers being greater than a certain number

There are total of n balls in k boxes. Box one contains n1 balls, box 2 contains n2 balls and so on. The probability of picking balls from boxes is p1,p2,...,pk. We can pick either all the balls in a ...
4
votes
2answers
174 views

Limit of certain recurrence relation

So given this recurrence relation (not how it was presented, but equivalent and much nicer) $$ x_{n+1} = \dfrac{x_n + nx_{n-1}}{n+1}; \ x_0 = 0,\ x_1 = 1 $$ I just can't find what the limit as $n$ ...
2
votes
2answers
72 views

recurrence relation Homework question 1

This is a HW question Find the recurrent relations for $a_n, n\geq 0$ where $a_n$ is the number of $n$character upper case words that contain exactly one $A$ We are only required to find the ...
1
vote
0answers
223 views

Recurrent relation for number of ways to get a balanced n-binary tree

In answering a question related to binary trees, I came up with the following recurrent relation: Base cases: $$ f \left (1 \right ) = 1 $$ $$ f \left (2 \right ) = 2 $$ Recurrent relations: $$ f(n) ...
1
vote
1answer
93 views

Recurrence $a_{n+1} = xa_n$ using generating function

I read the generating functionology, where author handles $$b_k(x) = {x \over 1-kx} b_{k-1}(x) = {x ^k \over (1-x)(1-2)(1-3x) \cdots (1-kx)}$$ since $b_0(x) = 1.$ I see that if denominator $(1-kx)$ ...
3
votes
1answer
73 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
79 views

What are the coefficients of the polynomial inductively defined as $f_1=(x-2)^2\,\,\,;\,\,\,f_{n+1}=(f_n-2)^2$?

Let $\{f_n(x)\}_{n\in \Bbb N}$ be a sequence of polynomials defined inductively as $$\begin{matrix} f_1(x) & = & (x-2)^2 & \\ f_{n+1}(x)& = & (f_n(x)-2)^2, &\text{ for all ...
1
vote
0answers
33 views

Whether recursive relationship is a different version of principle of mathematical induction?

In connection with the question I can't get satisfied with such 'so on' type logic. Is there a better way to solve it? and the responses recieved I would like to know whether ...
1
vote
0answers
60 views

Solving a recurrence involving binomials.

Does anybody know how to solve the following recurrence? Maybe with generating functions? Any hint? $t(n) = 1 + \frac{1}{2^{n-1}} \sum_{i=0}^{n-1} {n \choose i} t(i)$
2
votes
2answers
430 views

Nested roots sequence, how to prove it's monotone and bounded?

Let $a\ge1$ and define the sequence $(x_n)$ recursively by: $$x_1 = \sqrt{a}$$ $$x_{n+1}= \sqrt{a+x_n}$$ Here's what I did: Plugging in some values makes it seem as if the sequence is increasing. I ...
2
votes
1answer
283 views

Recurrence relation for $n$ numbers in which no 3 consecutive digits are the same.

I am stuck on trying to find (and solve) a recurrence relation to find all n-digit numbers in which no 3 consecutive digits are the same. These numbers are in decimal expansion. Now I first ...
2
votes
2answers
119 views

How do I solve the following recurrence?

Solve the recurrence $$X_n =\begin{cases} n & 0 \leq n < m\\ X_{n-m} + 1 & n \geq m.\end{cases}$$ So I've started with several base cases, but since the answer depends on $n$'s ...