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

learn more… | top users | synonyms (2)

0
votes
0answers
19 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
70 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
70 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
79 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
42 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
31 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
185 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
50 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
40 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{ ...
2
votes
1answer
70 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 ...
3
votes
1answer
44 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
46 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
47 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
54 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
68 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
27 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
0answers
19 views

Counterexample to a generalization of Gilbreath's conjecture

Consider the arrays with "initial conditions" $L_1^1>0,\ L_{n+1}^1>L_n^1,\ L_1^{i+1}=1$ satisfying the recurrence $L_n^{i+1}\in\{L_n^i-L_{\large{\inf\{m\in\Bbb Z_{>n}:L_m^i\leq ...
0
votes
1answer
65 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
19 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
24 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
46 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
21 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
52 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
42 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
63 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. ...
0
votes
0answers
52 views

Find a recurrence relation for the number of regions created by n mutually intersecting circles on a piece of paper.

Find a recurrence relation for the number of regions created by n mutually intersecting circles on a piece of paper (no three circles have a common intersection point).
1
vote
2answers
349 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
17 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
30 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
47 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 ...
0
votes
2answers
131 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 ...
0
votes
1answer
18 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
75 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
29 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 ...
0
votes
3answers
40 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
0answers
15 views

Find $R[r] \mod M $ where R is a recurrence relation and M can be any integer?

Let N,M are two constant integers and they may or not be prime . A recurrence relation R is defined as using N $R[1]=1$ , $R[r]=\frac{R[r-1]\space * \space p}{r^r}$ , where $p = {(N-r+1)}^{(N-r+1)}$ ...
0
votes
1answer
18 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
54 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
38 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 ...
-1
votes
1answer
45 views

need the steps on how to do this recurrence relation question

Given $T_0=0 $ and $T_n=T_{n−1}+n \forall n\in \mathbb N$ use the method of substitution to derive an explicit formula for $T_n$. Prove the validity if your formula.
-2
votes
3answers
53 views

recurrence relation stairs problem

Find a recurrence relation for S(n) the number of ways to climb n stairs if the person climbing can take one stair or two stairs at a time. What are the initial conditions?
1
vote
0answers
62 views

Trace and transpose of a Matrix

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1 =sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2} =\frac{s}{n+2}\{ R_{n+1} ...
1
vote
2answers
58 views

Finding an approximation for the difference of $a_n = \frac{1}{1+a_{n-1}}$ and it's limit.

I've got the recurrence $\displaystyle{a_{n} = {1 \over 1 + a_{n - {\tiny 1}}},\ }$ for $0 < a_{0} < 1 $ which has the solution $\displaystyle{\alpha = {\,\sqrt{\, 5\,}\, - 1 \over 2}}$ I am ...
3
votes
2answers
157 views

Solving a 2 independent variables (2nd degree) recurrence relation

Changes to the recurrences and definition are changed! See here: $f(n, 1) = 2n^2 $ and $f (n, k) = 0$ for $k \geq 2n$ and for $k < 0$ and $f(n, 2n-1) = 1$ for all $n$. Question: Is it possible ...
5
votes
1answer
54 views

Recursive identity for elliptic lattice constants $\sum_{\lambda\in\Lambda\setminus0} \lambda^{-2k}$

I am stuck on Exercise 3 in these notes. To keep this question self-contained: we have $\displaystyle\Lambda=\langle\omega_1,\omega_2\rangle=\omega_1\Bbb Z+\omega_2\Bbb Z\subset\Bbb C,$ ...
2
votes
1answer
103 views

Prove the summation involving Stirling numbers of the first kind

I have been trying to prove or disprove this for 2 days now, but i don't even know where to begin. $$ 1 = \sum_{m=1}^{n} \sum_{k=1}^{n} \frac{x^{n-m}(-1)^{n-k-m} \left[\matrix ...
1
vote
1answer
24 views

Another quick induction question for a recursively defined sequence (with closed form formula given)

I was given: A sequence is defined recursively by $a_0 = 1$, $a_1 = 4$, and for $n\ge2$, $a_n = 5a_{n-1} - 6a_{n-2}$. Use induction to prove that the closed form formula for $a_n$ is $a_n = ...
0
votes
0answers
36 views

How to solve recurrence relation $T(n)=2T(n/2)+4^n$ using characteristic equation method?

With change of variables $n = 2^k$ We get $$T(2^k) = 2T(2^{k-1}) + 4^{2^k}$$ which yields $$S(k) = 2S(k-1) + 4^{2^k}$$ I cannot go further. Here: ...
0
votes
1answer
36 views

Solution to recursion equation

Solve the recursive equation $$ T(n) = T(n-1) * T(n-2) $$ with $T(1) = a$, $T(2) = b$ How do I solve this algebraically? I unrolled the recursion and got a solution of $a^{f_n}b^{f_{n+1}}$, ...
0
votes
1answer
58 views

A Difficult Recursive Equation

I've got a recursive equation of the form $$ x_{n+1} - x_{n} = \frac{(-1)^n}{2 \cdot 4 \cdot 6 \cdot ... \cdot 2n}(x_0-x_1)$$ for $n \geq 2$. We can assume $x_0$ and $x_1$ are just real numbers/ I ...