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

learn more… | top users | synonyms

-2
votes
2answers
100 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
37 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
78 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
17 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
42 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
1answer
42 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 ...
2
votes
3answers
70 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
3
votes
2answers
98 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
308 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
47 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
42 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
30 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
15 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
2answers
34 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
29 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
22 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
46 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
76 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 ...
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
55 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
2answers
87 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
30 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
30 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
114 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
49 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
39 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
25 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
42 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
39 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
35 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
26 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 ...
0
votes
1answer
45 views

Count how many arrays of a specific type exist - O(N) Dynamic Programming

Consider an array of N + 2 binary digits (1 and 0), which contains at least one '1' and three '0'. The last and first digit of the array is 0. Given two numbers, let's say p and q, determine how many ...
0
votes
0answers
36 views

Recurrence Relation for the checkerboard problem

Im trying to come up with an accurate recurrence relation for the checkerboard problem given here (http://www.8bitavenue.com/2011/12/dynamic-programming-moving-on-a-checkerboard/). A recursive ...
0
votes
2answers
45 views

If infinitely many points of a sequence are given, is it possible to find out the recurrence relation?

I was thinking about sequences and stumbled upon a concept. If infinitely many points of a sequence are given, is it possible to find out the recurrence relation? Please enlighten.
1
vote
1answer
78 views

Recurrence relation to calculate the number of strings of $n$ characters that don't have consecutive vowels.

How can I find a recurrence relation to calculate the number of strings of $n$ characters (english alphabet, lowercase) that don't have consecutive vowels. It's clear that for $n = 1$ the result is ...
0
votes
2answers
37 views

Solving a Linear Recurrence Relation

I made quick progress on this, and then of course got stumped, so here's the problem: $$a_0 = -1, a_1 = -2, a_n = 4a_{n-1} - 3a_{n-2}$$ So, following the way I was taught to solve this type of ...
3
votes
2answers
300 views

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
0
votes
1answer
29 views

Inductive Proof Recursive Definition

Using this recursive Definition: $$a_{n} = \left\{\begin{matrix} 4 & n=1\\ a_{n-1}+4n-5 & n \geq 2 \end{matrix}\right.$$ I somehow have to prove using induction $$a_{n} = 2n^{2} - ...
1
vote
3answers
80 views

Strategies for developing explicit formulas for nth term given recurrence relation?

I'm wondering if there's any general strategies to develop an explicit formula for the nth term when you're given a recurrence relation. For example, I'm given a recurrence relation: $a_{n+1}=2a_n+1$ ...
0
votes
0answers
33 views

General solution of the recurrence equation with real shifts

How to find a general solution of the following functional (recurrence) equation: $$f(x) = c_1 f(x - a_1) + \dots + c_n f(x - a_n), \tag{1}$$ where $c_i, a_i$, $i = 1, ... n$ are arbitrary real ...
1
vote
1answer
19 views

Convergence and recurrence

I am asked to prove that $\sum\limits_{n=1}^\infty {\sin(n)\sin(n^2)\over n}$ converges using the following fact: Let $(a_n)_{n=1}^\infty$ be a bounded sequence. Then $\sum\limits_{n=1}^\infty ...
2
votes
1answer
67 views

Recurrence relation converting to explicit formula

Let $a_n = -2a_{n-1 }+ 15a_{n-2 }$ with initial conditions $a_1 = 10 $ and $a_2 = 70$. a)Write the first 5 terms of the recurrence relation. b)Solve this recurrence relation. c)Using the explicit ...
3
votes
1answer
67 views

Solving a recurrence for a random walk revisited

I previously asked about the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < ...
3
votes
2answers
87 views

a manipulation of Fibonacci recurrence

Let $F_n$ be the Fibonacci number, and we know $F_{n+2} = F_{n+1} + F_{n} $ with $F_0 =1,F_1 = 1$ And this can be manipulated to $F_{n+6} = 4F_{n+3} + F_n$ if we let n be a multiple of 3, we can ...
1
vote
2answers
66 views

number theory of coefficients in an infinite sequence of polynomials

EDIT: equivalent formulation by Hurkyl in comments: if $n$ is odd and $p^\nu \parallel n$ and $n > 2k,$ then $$ p^{(\nu + 2 + 2 k - n)} \; | \; \sum_j \left( \begin{array}{c} n \\ 2j \end{array} ...
4
votes
1answer
87 views

Recurrence for random walk

I have the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < x$ $p_i = 1$ if ...
0
votes
2answers
32 views

How to get the characteristic equation from a recurrence relation of this form?

I've been getting the characteristic equation from relations of the form $$U_n=3U_{n-1}-U_{n-3}$$ Thanks to this question I made before: How to get the characteristic equation? Now, I recently ...
1
vote
3answers
35 views

Finding the limit of a recurrence relation?

I have a sequence defined by the relation $$x_{n+1} = \alpha x_n + (1-\alpha)x_{n-1}$$ for $n\geq 1$, and I want to find the limit in terms of $\alpha , x_0,x_1$. I tried to do this by setting up a ...