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

learn more… | top users | synonyms

0
votes
1answer
15 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} $$
-2
votes
1answer
30 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} ...
2
votes
2answers
31 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$ ...
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 ...
1
vote
5answers
624 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 ...
2
votes
3answers
40 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 ...
0
votes
0answers
14 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 ...
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 ...
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.$$
1
vote
0answers
34 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: ...
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
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
votes
2answers
64 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
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
vote
2answers
59 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} $$ ...
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
23 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 ...
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} = ...
2
votes
3answers
59 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 ...
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 ...
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
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 ...
3
votes
2answers
82 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), ...
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
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 ...
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
20 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$$ ...
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) = ...
1
vote
1answer
17 views

How to solve non-homogeneous recurrence relations?

I have been looking around for a general method to solve non-homogeneous recurrence relations. Solving non homogeneous recurrence relation seems to be having almost the same problem as me. There is ...
0
votes
0answers
20 views

Non homogenous Recurrence Relation Problem

Consider the recurrence relation $$b[n] = b\left[ \frac{n}{2} \right] + b \left[ \frac{n+1}{2} \right] + 2$$ for $n > 1$ with $b[1] = 0$. Solve the recurrence in the case that $n$ is a power of $2$ ...
0
votes
1answer
20 views

Find a sequence $a$ so that $a_n = s \Delta a_n $.

Let $s$ be a real number $ s \ne 0 $. Find a sequence $a$ so that $a_n = s \Delta a_n $ and $a_0 = 1$. Any help with this question will be great. This is my first time doing recurrence relations ...
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 ...
0
votes
2answers
45 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
25 views

Need help with recurrence relations in general as well as specific problem

I am supposed to find the unique solution for a recurrence relation and I literally have no idea what to do. Here is what the professor did for us in class: \begin{align*} 3a_{n+1} - 4a_n &= 0 ...
0
votes
0answers
36 views

Total Time for a ball that bounces from a height of 8 feet and rebounds to a height 5/8 [duplicate]

I am trying to solve the following problem. Let's say a ball is dropped from a height of $8$ feet and rebounds to a height $\frac{5}{8}$ of its previous height at each bounce keeps bouncing ...
0
votes
1answer
32 views

Summation in recurrence

I search the entire forum and couldn't fint a solution to this. Can you please help me solve this recurrence equation? $$ T(n) = cn + \frac{4}{n^2}\sum_{k=0}^{n-1}T(k) $$
0
votes
0answers
23 views

need some guidance solving a recurrence

I've got this homework recurrence : $n^2T(n) = \sum_{k=0}^{n-1} 4T(k) + c \cdot n^3$ what I tried to do is to substitute n+1 to get : $(n+1)^2T(n+1) = \sum_{k=0}^{n} 4T(k) + c \cdot (n+1)^3$ and ...
0
votes
2answers
69 views

Total Time a ball bounces for from a height of 8 feet and rebounds to a height 5/8

I am trying to solve the following problem. Let's say a ball is dropped from a height of $8$ feet and rebounds to a height $\frac{5}{8}$ of its previous height at each bounce keeps bouncing ...
0
votes
1answer
28 views

Amount of numbers divisible by 3

Let $a_n$ be the amount of numbers consisting of $n$ digits from $\{1,2,3,4,5\}$ that are divisible by $3$ (giving an integer solution). I'm asked to proof that the following recurrence relation ...
0
votes
1answer
26 views

Simple recursion question

While reading these lecture notes: http://www.cc.gatech.edu/%7Evigoda/7530-Spring10/Kargers-MinCut.pdf, there is an recurrance relation: $$ {\rm P}\left(n\right) \geq 1 - \left[1 - {1 \over 2}\,{\rm ...
2
votes
1answer
45 views

Guess an explicit formula for recursively defined sequence

Was given this as a question. "Use iteration to guess an explicit formula for the recursively defined sequence and then prove that the formula is a solution to the recurrence using induction: ...
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 ...
0
votes
2answers
31 views

Solve Fibonacci-like linear recurrence equation

How to solve the following equation: $f(n) = f(n-1) + f(n-2) + 1$ My best guess is that it has something to do with Linear Recurrence Equation. I know how to do it without the constant $1$, which ...
0
votes
0answers
18 views

Generic Exponential curve base derivation

Alrighty so I am working on a computer program that forms ADSR envelopes including exponential curves for the attack, decay, and release segments. It uses the following equation for the exponential ...
0
votes
1answer
31 views

2nd Order Homogeneous ODE recurrence relation??

Doing some exam revision and have been stumped by this; the question asks you to find the recurrence relation satisfied by the coefficients. Attempt at solution: I have already found that there ...
0
votes
1answer
31 views

Hi guys, can anyone help with this recurrence relation problem?

I'm going through practice questions for my exams but this question has left me confused: The Bessel functions of integer order, Jn(x), are described by the generating function: Derive the ...
0
votes
1answer
23 views

Existence and Uniqueness of Solutions to First-Order Non-Linear Recurrence Relations

How do I go about proving the uniqueness of an existing solution to a recurrence equation of the form $$ a_{n+1} - f(n)a_n = 0 $$ ? Is there a theorem related to questions of uniqueness and ...
1
vote
0answers
23 views

Deriving recurrence relations, very stuck!

Going through past papers for my exams and cannot figure this one out, does anyone know how to do these? The Bessel functions of integer order, Jn(x), are described by a generating function of the ...