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

learn more… | top users | synonyms (2)

0
votes
1answer
122 views

Stability of equilibrium points

Given the difference equation and the continuously differentiable function $g$: $$x(n+1)=x(n)+h\times g(x(n))$$ Determine conditions on $h$ for which an equilibrium point is asymptotically stable, ...
1
vote
1answer
145 views

Finding recurrence relation for digits

codes have been generated odd number of odd digits. Let $ a_n $ be the number of valid n-digit activation codes. Find the recurrence relation. I can't figure out and understand the question. Can you ...
0
votes
1answer
78 views

Setting up a matrix from a recurrence relation to find diagonal matrix?

Considering the recurrence $F_n= F_{n−1}+3F_{n−2}−2F_{n−3}$ where $F_0=0$, $F_1=1$ and $F_2=2$, use diagonalization to find a closed form of the expression. If the sequence is continued the numbers ...
0
votes
2answers
22 views

Unable to verify solution to difference equation $m_x - 2pqm_{x-2} = p^2 + q^2$

I want to verify that the solution to the difference equation $m_x - 2pqm_{x-2} = p^2 + q^2$ with boundary conditions $m_0 = 0$ $m_1 = 0$ is $$m_x = -\frac{1}{2}(\frac{1}{\sqrt{2pq}} ...
4
votes
1answer
140 views

All solutions of the recurrence relation

Find all solutions of the recurrence relation $$ a_n = 2a_{n-1}+15a_{n-219}-64a_{n-3}+k $$
0
votes
1answer
30 views

Recurrence Relation, a question about the relation between $A_n$ and $A_{n+1}$

Given the following recurrence relation: $$A_{n+1} = {1 \over 4(1-A_n) }$$ $$ A_1 = 0 $$ Can I safely assume that if- $$\forall n \in \mathbb{N}, \ A_n < 1/2$$ then $$\forall n \in \mathbb{N}, \ ...
0
votes
1answer
26 views

Log property in proof of Master theorem

The family of recurrence considered is of the form $$ T(n) = aT(n/b) + n^c $$ $a,b,c$ are integers. One case of master theorem states: if $c< log_b a$, then $T(n) = \Theta(n^{log_b a}) $. I have ...
3
votes
1answer
53 views

Closed Form Solution for Recurrence Relation

Is it possible to calculate the closed form solution for the following recurrence relation? $$ T(n) = T\left(\frac{n}{2}\right) + T\left(\frac{n}{2} + 1\right) + \frac{n}{2} $$ I am trying to teach ...
0
votes
1answer
25 views

Solution Verification: turning recurrence relation into asymptotic bound with master theorem

Here are some recurrences I think I've correctly converted to bounds. Please let me know if I am right or wrong. T(n) = 3T(n/3) + lg(n) = Θ(n) T(n) = 3T(n/6) + n = Θ(n) T(n) = 4T(n/2) + n^2 = ...
1
vote
1answer
114 views

Concrete Mathematics Josephus Problem: How to prove 1.17 & 1.18

On the last page of the Josephus problem where things get really general, we're shown the pretty slick radix changing recurrence & solution 1.17 & 1.18 f(j) = aj, for 1 <= j <= d; ...
0
votes
0answers
23 views

Tips on effectively representing this recurrence relation in a generalized form.

The recurrence relation is $$ y_n = d_1 y_{n-1}+\frac{d}{dx}[y_{n-1}] $$ a good thing to note as well is $$ \frac{d}{dx}[d_n] = d_{n+1} $$ This is terrible to expand out after a good while, The main ...
1
vote
2answers
42 views

A second order problem on recurrence relation equals 3^n

I had this Recurrence Relation problem: $a_{n+2} + a_{n+1} - 12a_n = 0$ And I solved in a form like this $a_n = A(r_1)^n + B(r_2)^n$ $r^{n+2} + r^{n+1} - 12r^n = 0$ ...
0
votes
2answers
45 views

Define a sequence of integers $H(n)$ by $H(0) = 1$, $H(1) = 3$ and $H(n+1) = H(n) + H(n-1)$?

Then show that $H(n)$ can be expressed in the form $a\cdot(\psi(1))^n + b\cdot(\psi(2))^n$ and that $\psi(1)$ and $\psi(2)$ are the same numbers that occur in the proof of the Fibonacci numbers. I'm ...
0
votes
0answers
26 views

Second Order Recurrence Relation with Exogenous Forcing Sequence

I am solving an infinite horizon maximization problem, which yields as FOC second-order recurrence relation $A_{n+1} = \delta A_{n+2} + \delta A_{n} + c_n$, where $\{c_n\}_{n=0}^\infty$ and ...
3
votes
2answers
76 views

Show that it is the solution of the recurrence

I have to show that the solution of the recurrence $$X(1)=1, X(n)=\sum_{i=1}^{n-1}X(i)X(n-i), \text{ for } n>1$$ is $$X(n+1)=\frac{1}{n+1} \binom{2n}{n}$$ I used induction to show that. I have ...
2
votes
1answer
289 views

Find and solve a recurrence relation for the number of n-digit ternary sequences in which no 1 appears to the right of any 2.

Find and solve a recurrence relation for the number of n-digit ternary sequences in which no 1 appears to the right of any 2. $a_1=3$ and $a_2=8$ I am having trouble creating the recurrence relation ...
3
votes
3answers
94 views

Solve the recurrence relation $a_n=3a_{n-1}+n^2-3$, with $a_0=1$.

Solve the recurrence relation $a_n=3a_{n-1}+n^2-3$, with $a_0=1$. My solutions: the homogeneous portion is $a_n=c3^n$, and the inhomogeneous portion is $a^*_n=-1/2n^2-3/4n+9/8$. This results in a ...
0
votes
1answer
48 views

If the average of 2 successive years’ production 1/2($a_n + a_{n-1}$) is 2n + 5 and $a_0=3$, find $a_n$.

If the average of 2 successive years’ production $\frac{1}{2}(a_n + a_{n-1})$ is $2n + 5$ and $a_0=3$, find $a_n$. I started by solving for $a_n$ and got: $a_n = 4n+10-a_{n-1}$ but I am unsure how to ...
2
votes
0answers
42 views

Solve the recurrence $T(n)=aT(n-1)+bn$

I have to solve the following recurrence, given $T(1)=1$, $$T(n)=aT(n-1)+bn$$ I have done the following: $$T(n)=aT(n-1)+bn \\ =a^2T(n-2)+ab(n-1)+bn \\ =a^3T(n-3)+a^2b(n-2)+ab(n-1)+bn \\ = \dots \\ ...
5
votes
1answer
254 views

Solving a recurrence with diagonalization?

Considering the recurrence $F_n=F_{n-1}+3F_{n-2}-3F_{n-3}$ where $F_0=0$, $F_1=1$ and $F_2=2$. Use diagonalization to find a closed form expression for $F_n$. So I first continued the recurrence to ...
1
vote
2answers
51 views

The convergence of a recurrcively defined sequence.

Let $a_1=\sqrt{2}$ and $a_n=\sqrt{2+a_{n-1}}$ determine the convergence of the sequence and find its limit. I know the sequence converges to $2$ and i can show this informally. But I don't know how ...
0
votes
1answer
47 views

Solution of recurrence

I need some explanations at the proof of the following theorem. Theorem: Let $a$, $b$ and $c$ be nonnegative constants. The solution to the recurrence $$T(n)=\left\{\begin{matrix} b & ,\text{ ...
3
votes
1answer
95 views

New Identities for Generalized Fibonacci Numbers?

Over the past few months I have been investigating one the generalizations of the Fibonacci numbers, called the Generalized Fibonacci Numbers (GFNs). The GFNs are just like the regular Fibonacci ...
4
votes
1answer
73 views

A general or simple method to solve this iterative/recursive problem?

I have the following iteration $$ y_n\mapsto n\sum_{m=1}^{n+1}y_m $$ starting with $y_1$ being a positive real number. Is there a standard method to find the coeffcients of all $y_n$ after ...
1
vote
1answer
76 views

How to find the basic reproductive number of a discrete SIS epidemic model

I have been following a textbook called Mathematical Models in Population Biology and Epidemiology. The SIS model is given by the system \begin{aligned} S_{n+1} &= \Lambda + S_n e^{-\mu} ...
3
votes
2answers
51 views

How does the recursion relation work in the solution to this differential equation (using series)?

Sorry for the vague title but it would not let me post the first step and last step of this equation (too many characters!). How does $$\dfrac{a_0}{3n(3n-1)(3n-3)(3n-4)\cdots 9 \cdot 8 \cdot 6 \cdot ...
2
votes
2answers
80 views

Proving $\lim _{n\to \infty }a_{n+1}=\lim _{n\to \infty }b_{n+1}$ where $a_{n+1}=\frac{a_n+b_n}{2}\:$, $b_{n+1}=\sqrt{a_n\cdot \:b_n}$

$a_1,\:b_1>0$ $a_{n+1}=\frac{a_n+b_n}{2},\:b_{n+1}=\sqrt{a_n\cdot b_n}$ The question asks to prove that: $\lim _{n\to \infty }\left(a_n\right)=\lim \:_{n\to \:\infty \:}\left(b_n\right)$. ...
0
votes
3answers
300 views

Solving Linear Recursion with backtracking

What am I doing wrong? Is there a missing step? Tried googling but cannot seem to get it. Question: $$\begin{align} a_{n} &= a_{n-1}+2n+3 ,\\ a_{0} &= 4 \end{align}$$ Things I did: ...
0
votes
2answers
35 views

Show recurrence $T(n)=2*T(n-2)+3$ satisfy $T(n)=O(2^{n/10})$

Well the original question was asking about Tower of Hanoi. First I need to come up with a recurrence for the Tower of Hanoi with 4 poles. (Please note the original tower only consist of 3 poles) The ...
0
votes
1answer
140 views

Find a system of recurrence relations foe computing the number of n-digit quaternary sequences with

Find a system of recurrence relations foe computing the number of n-digit quaternary sequences with (a) An even number of 0s (b) An even total number of 0s and 1s (c) An even number of 0s and an even ...
0
votes
1answer
24 views

Reducing summation in recurrence relation

I am trying to solve this recurrence relation: $T(n) = 7T(\frac{n}{2}) + 18(\frac{n}{2})^2$ which is for Strassen's fast matrix multiplication. However I am stuck on trying to reduce the summation. I ...
2
votes
2answers
27 views

Help proving this recurrence relation?

Let $P_n$ be the number of strings of length n formed from letters A, B, C, E, O, that do not contain two consecutive consonants (that is, B or C). For example, AABOCA and BACOOEBO satisfy this ...
0
votes
2answers
50 views

How to solve this recurrence relation $f_n = 13{f_{n-2}} + 12{f_{n - 3}} + 2n + 1$?

$f_n = 13f_{n-2} + 12f_{n - 3} + 2n + 1$ Ok so first I was to find the solution for the $13f_{n-2} + 12f_{n - 3}$ portion. There are 3 roots, however, so I am not sure which ones to use in my general ...
0
votes
1answer
24 views

An induction proof in a set.

I have an induction problem that I have no idea how to start. So the question goes like this. Let $x_1=1$, $x_2=2$ and $x_n=x_{n-1} + 2x_{n-2}$. Prove that $x_n=2^{n-1}$ for all $n$ in the natural ...
2
votes
3answers
89 views

Finding recurrence relation for strings of length n formed from A, B, C?

Let $S_n$ be the number of strings of length $n$ formed from letters A, B, C, that do not contain substrings AB, BA, AAA or BBB. For example, for $n = 3$, all strings with this property are: AAC, ...
0
votes
1answer
64 views

Deriving the recurrence for the number of strings of length n?

(a) Let $P_n$ be the number of strings of length n formed from letters A, B, C, E, O, that do not contain two consecutive consonants (that is, B or C). For example, AABOCA and BACOOEBO satisfy this ...
0
votes
1answer
158 views

What is the difference between Difference equations and Recurrence relations?

Is there any difference between Difference equations and Recurrence relations? Some people are use them as difference equations and some are use as recurrence relations. I couldn't find in anywhere. ...
2
votes
2answers
2k views

A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1s.

A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1s. (A binary sequence only uses the numbers 0 and 1 for those who don't know) B) Repeat for ...
2
votes
0answers
21 views

Finding Recurrence Relation in Closed Form or as Infinite Summation/Coproduct

My recurrence relation is: $$f(n)=(2n-3) f(n-1) -x^2 f(n-2)$$ Where $$f(-1)=1$$ $$f(0)=0$$ $$f(1)=-x^2$$ $$f(2)=f(1)$$ $$f(3)=-x^2 (3-x^2)$$ And it gets more complicated from there
1
vote
1answer
33 views

Help to describing a recurrence for $l_n$

I have to describe a recurrence for $l_n$, the number of lobsters caught in year $n$. The task says: a hobby fisherman estimates the number of lobsters he will catch in a year as the average of the ...
0
votes
1answer
60 views

Making reccurence relation

I have trouble in understanding how to make recurrence relations. I read some of the questions on stack exchange but this stuff is not intuitive to me. For example, when we want to find a number of ...
1
vote
2answers
313 views

Find a recurrence relation for the number of ways to go n miles by fast walking at 2 miles per hour or

A) Find a recurrence relation for the number of ways to go n miles by fast walking at 2 miles per hour or jogging at 4 miles per hour or running at 8 miles per hour; at the end of each hour a choice ...
2
votes
1answer
37 views

Limit of the sequence determined by $x_{n+1} = x_n +\frac1{n(n+1)}$ [duplicate]

For $n \in \mathbb{N}$, let $x_{n+1} = x_n +\frac{1}{n(n+1)}$ and let $x_1 = 2$. Show that $\lim_{x\to\infty}x_n$ exists and determine this limit.
0
votes
1answer
23 views

How can i find the complexity of this recurrence relation?

Basically i'm having this recurrence relation which i don't know how to get the complexity of it by using the iterative method $T(n) = \begin{cases} 0, & \text{if $n=0$} \\ 1, & \text{if ...
2
votes
0answers
78 views

A similar, but hopefully easier problem than Gilbreath's conjecture

Gilbreath's conjecture says that for every positive integer $n$, if we write out the first $n$ primes $2,3,5,7,11,13,\ldots,p_n$ take the differences between consecutive terms ...
0
votes
1answer
53 views

Recurrence Equation and Markov Chain: How to get the base case

I established the reccurence equation for a Markov Chain but are not able to finde the base cases. We are interested in whether the sum of $t$ throws of a fair die is divisible by $k$ for some $k ...
1
vote
3answers
50 views

Inhomogeneus recurrence relation $a_{n+1} = 2a_n+3^n+4^n$

So this was given in class and the teacher weren't able to solve it, and I was wondering how a solution can be given? $a_{n+1} = 2a_n+3^n+4^n, \enspace a_0 = 1$ Usually we'd consider the ...
0
votes
1answer
21 views

Proof by Induction Question - as part of Russo Dye Theorem

I began with $x_{n+1} = \displaystyle \frac{x+x_n}{2}$ and did the first few iterations to find that it follows this pattern: $\displaystyle \frac{(2^n-1)x+x_0}{2^n}$. How can i show this is true for ...
2
votes
1answer
60 views

How many recurrence relations are possible for a sequence? [closed]

How many recurrence relations are possible for a sequence? Example: $$ 5, 11, 29, 83, 245, \ldots $$ We have two recurrence relation: $T_n = 3T_{n-1} - 4$ $T_n = T_{n-1} + 6 \cdot 3^{n-1}$ Both ...
0
votes
1answer
84 views

Using Difference Equations to Solve Word problems

While I was studying about finite differences I noticed a question in difference equations.Does anyone knows how to solve this using difference equations? WORD PROBLEM Imagine you are to jump from ...