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

learn more… | top users | synonyms

0
votes
1answer
18 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
1answer
31 views

All solutions of the recurrence relation

Find all solutions of the recurrence relation $$ a_n = 2a_{n-1}+15a_{n-2}-36a_{n-3}+2^n $$ Hint: Find both the homogeneous and particular solutions. You can leave the homogeneous solution with ...
0
votes
0answers
11 views

Problem in understanding the proof of master theorem case

I am going through the proof of master method or master theroem. This is the formula that is been given by the author for the Total Work =Cn^d*(∑(a/b^d)^j) where value of J=0 to logbn as per the ...
0
votes
1answer
24 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
14 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 ...
2
votes
1answer
21 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
11 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
28 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
11 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
31 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
32 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
11 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 ...
-1
votes
0answers
26 views

Show that any linear combination of solutions to:

Show that any linear combination of solutions (in $a$) to: $$a_n=c_1a_{n-1}+c_2a_{n-2}+...+c_ra_{n-r}$$ is also a solution to the equation.
3
votes
2answers
54 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
40 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
61 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
32 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
28 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 \\ ...
4
votes
0answers
54 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
48 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
24 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 ...
2
votes
1answer
28 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 ...
3
votes
1answer
14 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
44 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
35 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
23 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
26 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
13 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
19 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
0answers
4 views

Particular solution to Cn-B (recurrence relation)(easy)

I have a non-homogeneous equation. I can find the general solution to the homogeneous part but say $T(n) = 2n+1$ where $T(n)$ is just the auxiliary or complementary equation. what is the particular ...
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
41 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
34 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
31 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
24 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
25 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
77 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
27 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
12 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
38 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
1answer
17 views

Sn−1 Sn-2 Sn−3 pattern generalize it n-k substitute for base case prove by induction..need to know how to do this question using these steps

A sequence $S_0,S_1,S_2,\dots$ is defined recursively as follows $S_0:=3,\quad$$S_n:=S_{n−1}+2n$ for $n≥1$ Calculate a few terms and conjecture a formula for $S_n$ as a function of $n$. Prove the ...
0
votes
2answers
56 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
32 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 ...