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

learn more… | top users | synonyms

0
votes
1answer
9 views

How should I find the analytical form of these recursive equations

I have $$x_1(t+1) = (1-m \rho_1)x_1(t) + n\rho_2 x_2(t) + h1$$ $$x_2(t+1) = (1-m \rho_2)x_2(t) + n\rho_1 x_1(t) + h2$$ Suppose $x_1(0)$ and $x_2(0)$ are known. How can I find the analytical form of ...
0
votes
2answers
21 views

Domain and range transformation

How can I solve this recurrence relation using Domain and Range transformations: $$ \begin{array}{rcl} n^2 a_n &=& 5(n-1)^2 a_{n-1} +2 \\ a_0 &=& 0 \\ \end{array} $$
1
vote
1answer
41 views

Find the generating function for a series , given a recurrence relation

I am solving a problem on an Online Judge. The problems solution boils down to find the solutions to the following recurrence relation: ...
0
votes
1answer
61 views

Induction proof with no terms of sequence

The sequence $[x_n]$ is given by $x_1=1$ and $x_{n+1}=\displaystyle\frac{4+x_n}{1+x_n}$ for $n\ge 1$. Prove by induction that for $n\ge 1$, ...
2
votes
2answers
34 views

Maximum of a function from integers to integers

Suppose $f$ is a function form positive integers to positive integers satisfying $f(1)=1$, $f(2n)=f(n)$, and $f(2n+1)=f(2n)+1$ for all positive integers $n$. Job: Find the maximum of $f(n)$ when $n$ ...
-2
votes
1answer
31 views

How should I proceed to solve this recurrence relation: $T(n) = T(n - 1)^2$

I tried to solve this recurrence relation, but I was confused when I had to determine the pattern. $$ T(n) = \begin{cases} 3, & \text{if }n = 0 \\ T(n - 1)^2, & \text{if }n > 0 \end{cases} ...
0
votes
1answer
17 views

Recurrence relations :rate of growth

Consider the multiplication of bacteria in a controlled environment. Let ar denote the number of bacteria there are on the r-th day. We denote the rate of growth on the r-th day to be ar- 2(ar- 1). If ...
2
votes
3answers
42 views

Proof by induction of a recursive sequence

I am studying CIE A levels Further Maths and I am stuck at a question from June 2002: Q The sequence of positive numbers $u_1,u_2,u_3,...$ is such that $u_1<4$ and ...
2
votes
5answers
627 views

Explanation of recursive function

Given is a function $f(n)$ with: $f(0) = 0$ $f(1) = 1$ $f(n) = 3f(n-1) + 2f(n-2)$ $\forall n≥2$ I was wondering if there's also a non-recursive way to describe the same function. WolframAlpha tells ...
1
vote
1answer
583 views

Solving a recurrence realtion using backward substitution.

So I've been trying my best to do this, and I have made some good progress, I just need to know if what I have done is correct and if not, what the hell am I doing wrong? :P I start off with this ...
0
votes
0answers
15 views

Find solution to recursion relation

Consider a following recursion relation: \begin{equation} a_s^{(m+1)} = s a_s^{(m)} 1_{s \le m} + a_{s-1}^{(m)} 1_{s\ge 2} \end{equation} for $s=1,\dots,m+1$ subject to $a^{(1)}_1= 1$. The solution ...
1
vote
3answers
35 views

Where is the error in finding the particular solution to this recurrence relation?

The question is to write the general solution for this recurrence relation: $y_{k+2} - 4y_{k+1} + 3y_{k} = -4k$. I first solved the homogeneous equation $y_{k+2} - 4y_{k+1} + 3y_{k} = 0$, by writing ...
5
votes
5answers
645 views

Solving a set of recurrence relations

I have the 7 following reccurence relations: $A_n = B_{n-1} + C_{n-1}$ $B_n = A_n + C_{n-1}$ $C_n = B_n + C_{n-1}$ $D_n = E_{n-1} + G_{n-1}$ $E_n = D_n + F_{n-1}$ $F_n = G_n + C_n$ $G_n = E_n + ...
0
votes
2answers
46 views

Use Bonnet recursion formula to prove by induction

Use Bonnet recursion formula: $P_{n+1}(x) = \frac{2n+1}{n+1} x P_n(x) - \frac{n}{n+1} P_{n-1}(x)$ to prove by induction 1) $P_n(1) = 1$ for all $n$ 2) $P_n(-x) = (-1)^n P_n(x)$ for all $n$ an for ...
1
vote
1answer
29 views

Hypergeometric function relation knowing initial value?

Is there a relationship or recurrence relation I can use to solve for $$\, _2F_1(b,r+k;a+b+k;p)$$ as a function of $k$, with known value of when $k=0$ $$ \, _2F_1(b,r;a+b;p) = f_0$$ (a,b,r,p) are ...
-1
votes
2answers
70 views

Using generation functions solve the following difference equation

Using generation functions solve the following difference equation $$ a_{n+1} - 3a_{n+2} + 2a_n = 7n ; n\geq0; a_0 = -1; a_1 = 3. $$
0
votes
1answer
34 views

Could someone explain me this induction.

I'm trying to understand a paper called "Diameter of Polyhedra: Limits of Abstraction" available here : http://sma.epfl.ch/~eisenbra/Publications/designs.pdf My problem is with the first two ...
3
votes
4answers
106 views

Closed form of a recurrence relation using generating functions

It's been awhile since I have done this. The sequence is $\displaystyle a_n = a_{n-1} + 5~a_{n-2}$ with $a_{0}=0$ and $a_{1}=1$. I found the generating function to be $\displaystyle G(x) = ...
0
votes
3answers
465 views

Finding Particular Solutions to Non-Homogeneous Recurrence Relations

Could anyone assist me in solving the following recurrence relations? $a_n = 3a_{n-1} - 2a_{n-2} + 2^n n^2$ $b_n = -nb_{n-1} + n!$ Specifically, I am not sure how to find the particular solutions ...
0
votes
3answers
554 views

non homogeneous recurrence relation

I am trying to solve the non-homogeneous linear recurrence relation: $$f(n) = 6f(n-1) - 5,\quad f(0) = 2.$$ How do I go about doing it? This is so different from solving a homogeneous recurrence ...
5
votes
4answers
163 views

Finding the general term of two related recurrence relations

I'm trying to find the general term of the recurrence relations $\quad a_{n+1}=a_n+\text hb_n$ $\quad b_{n+1}=b_n-\text ha_n $ $\quad a_0=0, \quad b_0=1$ I tried finding the terms, ...
9
votes
3answers
2k views

Solving recurrence relation in 2 variables

We already know how to solve a homogeneous recurrence relation in one variable using characteristic equation. Does a similar technique exists for solving a homogeneous recurrence relation in 2 ...
1
vote
2answers
14 views

Finding a particular solution for non-homogeneous recurrence relation [on hold]

The recurrence relation that I have is $$T(n) -5\ T(n-1) + 6\ T(n-2) = 2n.$$
0
votes
2answers
32 views

2nd order homogeneous difference equation

$$a_{n+2} = 9a_{n+1} - 18a_n,\quad n\geq 0,\,\,a_0=1,\,\, a_1=3$$ I got to the point where i moved all to LHS which gives me $a_{n+2} - 9 a_{n+1} + 18 a_n$ (correct me if I'm wrong). I then ...
2
votes
2answers
215 views

Solve the following non-homogeneous recurrence relation:

Find the solution to the following non-homogenous recurrence relation: $a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$ for $a_0=1, a_1 = 2$. I have found from the characteristic polynomial the general homogenous ...
2
votes
3answers
637 views

Summation in a recurrence relation

edited to reflect advice from the comments: While working on a generalization of a tiling problem, I generated a recurrence relation to describe the total number of possible tilings. The relation ...
0
votes
2answers
33 views

Higher order recurrence relation

I have the following non-homogenous recurrence relation and I'm trying to solve it using characteristics roots method : $a_n = 10a_{n-1} -37a_{n-2} + 60a_{n-3} -36a_{n-4} +4$ for $n \ge4$ and $ a_3 = ...
-1
votes
1answer
25 views

Which is a linear and homogeneous recurrence?

Which of the following choices is a linear and homogenous recurrence? $1)$ $A_n = A_{n-1} + 4A_{n-2} + 3n$ $2)$ $A_n = n + 1$ $3)$ $A_n = (A_{n-1})^2$ $4)$ $A_n = 5A_{n-1} + A_{n-2} + 3A_{n-3}$
1
vote
2answers
44 views

difference equation( recurrence relation)

Let $y_n$ satisfy the nonlinear difference equation: $$(n+1)y_n=(2n)y_{n-1}+n.$$ Let $u_n=(n+1) y_n$. Show that $$u_n= 2u_{n-1}+n.$$ Solve the linear difference equation for $u_n$. Hence find ...
1
vote
2answers
60 views

Get the Nth term of a sequence 1,2,4,7,13,24…

I have a sequence: 1,2,4,7,13,24,44,81, ... and I think it's like a Fibonacci sequence, however you add three number together and not two ("Tribonacci"?). So: $$ v_n = v_{n-1} + v_{n-2} + v_{n-3} $$ ...
4
votes
3answers
315 views

How do I resolve a recurrence relation when the characteristic equation has fewer roots than terms?

I know how to solve "simple" recurrence relations. For instance, say you have: $$c_0 = 20$$ $$c_1 = 30$$ $$c_n = 3 c_{n-1} - 2 c_{n-2}$$ We can write the characteristic equation as: $$3x^{n-1} - ...
4
votes
0answers
140 views

General overview about Recursion (free online texts)

I'm looking for free online texts about recursion. What I'm looking for formal definitions* of "all" (most of) the different types of recursion and from different points of views like Category ...
4
votes
3answers
808 views

Recurrence relation (linear, second-order, constant coefficients)

Q1. Find the general solution to the difference equation $$ a_{n} - 4a_{n-1} + 3a_{n-2} = 6 $$ Q2. Solve the difference equation $$ a_{n} - a_{n-1} - 2a_{n-2} = 0, a_0 = 2, a_1 = 4 $$ I am ...
2
votes
2answers
59 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 ...
0
votes
0answers
12 views

Series expansion in a recurrence relation (Lines in a plane)

L The recurrence is therefore L0 = 1 ; Ln = Ln−1 + n , for n > 0. The known values of L1 , L2 , and L3 check perfectly here, so we'll buy this. Now we need a closed-form solution. We could play ...
2
votes
2answers
24 views

Recurrence relation practice problem that I can't figure out

Thanks for taking the time to look at this problem. I'm trying to prepare for a test on Monday by doing some extra odd numbered problems from my textbook. I'm having a lot of trouble trying to solve ...
1
vote
3answers
91 views

Recurrence relations (Big-O notation)

Say I'm given a recursive function such as: function(n) { if (n <= 1) return; int i; for(i = 0; i < n; i++) { function(0.8n) } } ...
0
votes
0answers
23 views

Approximating the function $ f(x) = \frac{1}{1+a^2x^2} \text{with } a=4 \text{ in the interval }[-1,1]$ with Legendre Polynomials

Given: $$ f(x) = \frac{1}{1+a^2x^2} \text{with } a=4 \text{ in the interval }[-1,1]$$ Approximate the function $f(x)$ in the least squares sense using legendre polynomials up to order 2. The ...
1
vote
0answers
13 views

Almost complete multivariate recurrence solution…

$$ \gamma c_{jm_1m_2} = s^+_{jm_1}c_{j(m_1+1)m_2} - s^+_{jm_2}c_{jm_1(m_2+1)}\\ \gamma d_{jm_1m_2} = s^-_{jm_1}d_{j(m_1-1)m_2} - s^-_{jm_2}d_{jm_1(m_2-1)} $$ where $s_{jm_i}^{\pm} = ...
0
votes
1answer
25 views

help me finding the limit of sequence question

A 1= 1 and {A n}=root[1 + {A n-1}] B 1= 2 and {B n}=root[2*{B n-1}] help me Since I am studying math recently I need person`s help
2
votes
3answers
60 views

solution of a recurrence

How might one solve the recurrence $x_{n+1} + x_n + 2^n = 0$ given the necessary initial conditions ($x_0$)? Possible ideas I have in mind: 1) Generating functions 2) Discrete Laplace ...
1
vote
1answer
21 views

Does the order I multiply the characteristic equation's factors in the homogeneous solution matter?

I've been doing a recurrence relation exercise in my book. Doing some steps and comparing them to the ones taken by the book. $$T(0) = 1$$ $$T(1) = 2$$ $$T(k) - 7T(k-1)+10T(k-2)=6+8k$$ ...
2
votes
0answers
32 views

Linear Independence of Powers of “roots vector” [duplicate]

Let us be working over the field of complex numbers. Suppose $f(x)= a_n x^n + \cdots +a_1 x + a_0$ is a degree $n$ polynomial with $n$ distinct roots $z_1,\ldots,z_n$. Is the following matrix always ...
5
votes
5answers
280 views

What particular solution should I guess for this relation?

Just trying to solve a non-homogeneous recurrence relation: $$f(n) = 2f(n-1) + n2^n$$ $$f(0) = 3$$ Characteristic equation is: $$f(n) - 2f(n-1) = 0$$ $$a-2 = 0$$ $$a = 2$$ Homogeneous ...
0
votes
0answers
16 views

order definition [closed]

i'm in desperate need of your much appreciated expertise with trying to define the following order relation, guess it might be somewhat near a lexicographical order, not a straightforward alphabetical ...
0
votes
2answers
40 views

Recurrence Relationship Questions

Consider the recurrence defined by: $$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$ Determine what Gn is for several values of n to determine a formula for Gn. $2n$ $n$ $2n-1$ $n^2$ *I believe this one is ...
0
votes
2answers
45 views

Two sequences $a$ and $b$ for which $\Delta a_n = \Delta b _n$

Find two different sequences $a$ and $b$ for which $\Delta a_n = \Delta b_n$ for all of $n$. This is my first time doing recurrence relations, so if anyone could provide some thorough and clear ...
3
votes
2answers
83 views

Deriving a (tricky, I think?) recurrence relation

I'm having trouble trying to derive a recurrence relation for a problem I'm looking at. "Let $h_n$ be the number of ways of packing a bag with $n$ fruits (either apples, oranges, bananas, or pears), ...
1
vote
1answer
39 views

Simple Recurrence Questions [closed]

$r$ is a real number, define a recurrence relationship for $A_n$ $$A_0 = 1\\ A_n = r\cdot A_{n-1}$$ Question: What is the value of $A_4$ $4(A{n-1})$ $r^4$ $1$ $4r$ I've pretty much eliminated ...
1
vote
1answer
13 views

About the particular solution given an homogeneous solution in a recurrence relation.

If your recurrence relation's characteristic equation factorizes to $$(x+1)(x-5)^3 = 0$$ and $h(n) = 3+2n \implies f_p(n) = d_0+d_1n$ $h(n) = 7n+3^n \implies f_p(n) = ...