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

learn more… | top users | synonyms (2)

1
vote
2answers
49 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
37 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{ ...
0
votes
1answer
30 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
33 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
25 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
42 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
48 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
40 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
25 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
14 views

Exact closed form of recurrence $4F(n/4)+n^2$, $F(1)=1$, n is a power of 4

This is not a linear recurrence, my notes mentioned that solve non-linear recurrence by using the The Akra-Bazzi Formula. No examples was given , and I dont really understand what the formula is ...
0
votes
0answers
14 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
36 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
16 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
21 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
43 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
44 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
37 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
35 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. ...
-1
votes
0answers
26 views

characteristic equation for a recurrence equation

I know how to do the simple ones but how do we find the characteristic equation of a more complex equation say, $T_n = \alpha T_{n-2} + \beta T_{n-3} + \gamma n + \delta$ I'm just trying to cover ...
0
votes
0answers
20 views

Find a recurrence relation for the number $a_{n,m,k}$ of distributions of $n$ identical objects into $k$ distinct

Find a recurrence relation for the number $a_{n,m,k}$ of distributions of $n$ identical objects into $k$ distinct boxes with at most four objects in a box and with exactly $m$ boxes having four ...
0
votes
0answers
35 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
114 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 ...
1
vote
0answers
13 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
28 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
0answers
13 views

No of different permutations .. a recurrence relation needed

Given N similar red balls and M similar white balls. In how many different ways they can be arranged so that ...
0
votes
1answer
43 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
84 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
0answers
33 views

What are the main similarities between difference equations and differential equations, specifically in methods for solving them?

I know that that difference equations can be used to represent discrete dynamical systems and differential equations can be used to represent continuous dynamical systems. Therefore both are ...
0
votes
1answer
16 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
67 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
0answers
56 views

Recurrence Relations Q [duplicate]

A sequence $S_0,S_1,S_2...$ is defined recursively as follows $S_0:=3$ $S_n:=S_{n-1}+2n$ for $n\ge 1$ Calculate a few terms and conjecture a formula for $S_n$ as a function of $n$. Prove the ...
0
votes
1answer
23 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
38 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
17 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 ...
0
votes
0answers
48 views

Discrete maths - Recursion, formula and induction question

A sequence $S_{0},S_{1},\ldots$ is defined recursively as follows: $$ S_{0} = 3\,,\quad S_{k} = S_{k - 1} + 2k\quad\mbox{for}\quad k \geq 1 $$ Calculate a few terms of the sequence and conjecture a ...
-1
votes
0answers
13 views

Recurrence relations - Substitution [duplicate]

Given T0 = 0 and Tn= T n-1 + n for all natural numbers, n>= 1 use the method of repeated substitution to derive an explicit formula for Tn.
1
vote
1answer
17 views

How many recurrence relations are possible for a sequence?

How many recurrence relations are possible for a sequence? Example: 5, 11, 29, 83, 245, .... We have 2 recurrence relation: T(n) = 3T(n-1) - 4 T(n) = T(n-1) + 6*3^(n-1) Both give T(n) = 3^n + 2
0
votes
1answer
20 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
40 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
31 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
votes
1answer
25 views

Solution for $T(n) = 2T(\sqrt{n}) + log_2(n)$ [closed]

Solve for: $T(n) = 2T(\sqrt{n}) + log_2(n)$ with no base conditions.
1
vote
0answers
48 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
53 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 ...
0
votes
1answer
25 views

solving T(n) = 4T(n/2) + n^3 + n*(log(n))^2

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n) = 4T\left(\frac n2\right) + n^3 + n\cdot\log^2 n$$ i tried to solve this also with master method... ...
3
votes
2answers
146 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
45 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
79 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
17 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 = ...