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

learn more… | top users | synonyms

0
votes
0answers
26 views

Solution of Recurrence Relation for 1/2-integers

Suppose one wants to solve a recurrence relation of the form $$ c(m+1) - c(m)/f(m) = -g(m) $$ for $c(m)$. The general solution can be given by $$ c(m) = ...
1
vote
3answers
16 views

non-homogeneous recurrence relations

The question is: $a_{n}=12a_{n-2}+16a_{n-3}+9\cdot 4^{n}+81n$with $a_{0}=0 ,a_{1}=1 ,a_{2}=98$ I tried to deal with the particular solution first by: ...
0
votes
1answer
20 views

Recurrance Relation [on hold]

A sequence $\{u_n\}$ is generated by the recurrence relation $u_{n+1}= \frac{6}{u_{n-1}} , n≥1$ If $u_2=3u_1$ find the possible values of $u_1$ Find $u_3$ corresponding to each value of $u_1$
0
votes
1answer
33 views

Induction Proof of: Find $f(n)$ when $n=2^k$, where $f$ satisfies the recurrence relation $f(n)=f(\frac{n}2)+1$ with $f(1)=1$

How can I proof this using regular induction and strong induction? $$f(2^k)=f(\frac{2^k}2)+1=f(2^{k-1})+1$$ $$f(2^{1-1})=f(2^0)=f(1)=1$$ $$f(2^{2-1})=f(2^1)=f(2)=f(1)+1=2$$ ...
3
votes
4answers
72 views

Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$

$g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$ With initial conditions $g_{0} = 23, g_{1} = 37, g_{2} = 42 $ This is a practice question I'm working on, and I'm running into absurd amounts of ...
0
votes
0answers
26 views

Annihilators for an expression

Annihilators Problem What will be the annihilators for 2.n^2 + 3n? Thanks in advance.
-2
votes
0answers
19 views

Inequality in a recurrence relation. [on hold]

Let $(y_n)_{n=1}^\infty$ be a strictly increasing sequence of positive integers such that $2^{y_n} - 3^n > 0$, and let $(m_n)_{n=1}^\infty$ be the sequence of positive integers such that $m_1 = 1$ ...
0
votes
1answer
17 views

solution for recurrence relation, characteristic roots method.

For my characteristic roots method for solving a homogeneous recurrence relation, I got the roots for the equation as $2,2,3,3$. for satisfying the boundary conditions, will the general solution be ...
1
vote
2answers
44 views

Recurrence relation with generating function problem

I've got a recurrence problem that I'm close to solving, but having trouble with finishing up. Solve the following recurrence relation using generating functions: $$g_n = g_{n-1} + g_{n-2} + ...
0
votes
1answer
16 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
26 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
33 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
37 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 ...
2
votes
5answers
643 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
44 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
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 ...
0
votes
1answer
35 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
16 views

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

The recurrence relation that I have is $$T(n) -5\ T(n-1) + 6\ T(n-2) = 2n.$$
1
vote
1answer
42 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
30 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}$
-2
votes
2answers
83 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
61 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
25 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 ...
2
votes
3answers
61 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
84 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
281 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
42 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
40 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
22 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
18 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
50 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
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
35 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
25 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 ...