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

learn more… | top users | synonyms (2)

1
vote
0answers
28 views

Solving differential recurrence equations

I played around trying to make an equation describing Fibonacci numbers and ended up finding out that what I'd created was something called a recurrence equation: $f(x)=f(x-1)+f(x-2)$ ($f(x)$ is ...
7
votes
4answers
320 views

Limit of $x_n^3/n^2$ when $x_{n+1}=x_n+ 1/\sqrt {x_n}$ with $x_0 \gt 0$

Let $(x_n)_{n \ge 0}$ a sequence of real numbers with $x_0 \gt 0$ and $x_{n+1}=x_n+ \frac {1}{\sqrt {x_n}}$. Check the existence and find $$L=\lim_{n \rightarrow \infty} \frac {x_n^3} {n^2}$$ ...
1
vote
2answers
39 views

How to solve this homogeneous recurrence relation of 2nd order?

I have this homogeneous recurrence relation: $x_n = 3x_{n-1} + 2x_{n-2}$ for $n \geq 2$ and $x_0 = 0$, $x_1 = 1$. I form the characteristic polynomial: $r^2 - 3r -2 = 0$ which gives the roots $r = \...
0
votes
3answers
62 views

Solving a recurrence relation with n squared

I have trouble solving the following recurrence: $$a_{1}=1, a_{n}=a_{n-1}\cdot n^{2}$$ for $n>1$. It seems somewhat untypical to me, could you give me some general advice on dealing with such ...
5
votes
2answers
90 views

Functional Equation of iterations

Problem: Let $f : \mathbb{Q} \to \mathbb{Q}$ satisfy $$f(f(f(x)))+2f(f(x))+f(x)=4x$$ and $$f^{2009}(x)=x$$ ($f$ iterated $2009$ times). Prove that $f(x)=x$. This is a contest type problem ...
0
votes
3answers
44 views

How to solve this homogeneous recurrence relation

I have the homogeneous recurrence relation $x_n = x_{n-2}$ for $n \geq 2$ with $x_1 = 2$ and $x_0 = 1$. So for the characteristic polynomial I got $r^2 - r = 0$, then I factored out r: $r(r - 1)$ for ...
-1
votes
1answer
33 views

Recurrence relation in $2$ variables [closed]

Given a recurrence relation $func(n,k) = func(n-1,k) + func(n-1,k-1)$ with base cases $func(n,1) = n$ and $func(1,k) = 1$. How can I obtain its solution?
2
votes
1answer
48 views

Could Master Theorem be applied to this recurrence relation?

I have the following recurrence relation $T(n) = 4T(\frac{n+4}{2}) + n$ Is there some way in order to apply the Master Theorem to it? Or do I have to find an alternative approach in order to solve ...
0
votes
0answers
22 views

Solving a linear multivariable recurrrence

How do I solve a linear multivariable recurrence relation like the following: $$ f(x, y) = a f(x - 1, y) + b f(y - 1, x) + c $$ subject to the boundary conditions: $$ f(x, 0) = 0, f(0, y) = 1 $$ ...
0
votes
0answers
31 views

Recurrence relation connected with the continued fraction of the Exponential Integral.

I've been trying to solve this non-homogeneous recurrence relation with no luck. $$k_n=a_nk_{n-1}+k_{n-2}$$ $$a_n= \begin{cases} x, & \text{if $n$ is even}\\ -2/(n+1), & \text{if $n$ is odd} \...
1
vote
2answers
52 views

solutions of system that define by induction

I'm new on studying Systems of equations. I just want to know how to prove that solutions of this system of equations: \begin{align} a_0 &= 2\\ a_1 &= 1\\ a_2 &= -1\\ a_{n+1} &= a_n - ...
0
votes
2answers
46 views

Recurrence Relation with two parameters and Summation

This is a recurrence relation with two parameters which came up in a problem I was trying to solve. Given $$\begin{align}&A_n=pB_{n-1};\qquad &&B_n=q(A_{n-1}+B_{n-1})\\ &A_4=p; \...
1
vote
0answers
26 views

How many steps does this recursion take?

If $T(N)=2T(N^{1/3-\epsilon})$ then what can $T(N)$ be? Note if $\epsilon=0$ then $T(N)=2^{\log_3\log_2N}$ holds? $N^{1/3}=2^{\frac{\log_2N}3}$ $N^{1/9}=2^{\frac{\log_2N}{3^2}}$ and so should end ...
2
votes
1answer
107 views

Tough Recurrence Relation

I'm trying to find a recurrence equation solution to $$f(n)=a(n)f(n-1)+f(n-2)$$ with the initial conditions that $f(-1)=0, f(-2)=1$ and $$a(n)=\frac{c}{2}(1+(-1)^n)-\frac{d}{n+1}(1-(-1)^n)$$ with some ...
1
vote
1answer
19 views

Help With a proof involving the Ackermann function!

So, I'm continuing on with this computability text by Cutland, and I've reached the Ackermann function. Cutland says he will give a more rigorous proof that the function is computable later on, but ...
1
vote
0answers
35 views

Any way to characterize this family of polynomials?

I have a family of polynomials generated by the recurrence relation $P_{n+1}(w) = (1+w)P_n ^{\ \prime}(w) -(3n-1 +nw)P_n(w) \\ P_1(w) =1$ The family is related to the Lambert $W$-function by its ...
1
vote
2answers
28 views

conditions in which the repair shop process is recurrent (null\positive) or transient

here's the Story: Let $\epsilon_1.\epsilon_2,... $ be i.i.d numbers of machines for repair to the repair shop on mornings of days $1, 2,...$ . Assume that the shop is capable of repairing exactly K ...
2
votes
2answers
45 views

solution to the recurrence relation $a_n=\frac{n}{a_{n-1}}$

Is there a recurrence solution to $a_n=\frac{n}{a_{n-1}}$? I'm wondering if it could be done in the form of an alternating series partial to $n$ or as a trigonometric function.
11
votes
3answers
98 views

Recursive Sequence $a_n = \frac{1}{2} (a_{n-1} + 5) $

I got this question in which they ask me to explain why it is convergent and evaluate its limit. $$a_1=3\;and\;a_n = \frac{1}{2} (a_{n-1} + 5) \\ n=2,3,4,... $$ To prove it's convergent, I show ...
1
vote
0answers
49 views

Finding an explicit formula given this recursive definition

I have been considering the following problem: say you are picking from an infinite population of red and blue balls. A ball has a probability $p$ of being red; otherwise it is blue. If I choose $n$ ...
1
vote
0answers
35 views

Square summable solutions of second order difference equations

There should be a standard argument for the following claim: If the system of equations of the form $$a_{n-1}u_{n-1}+(b_{n}-z)u_{n}+a_{n}u_{n+1}=0, \quad n\in\mathbb{Z},$$ where $a_{n}\in\mathbb{C}\...
1
vote
0answers
36 views

Finding the limits to sequences given by recursive transformation of a vector: $a_n = a_{n-1}M$

I'm interested in finding limits to 'recursive vector sequences' of the form $a_n = a_{n-1}M$ (where $a$ is a vector and the matrix $M$ is a transformation of $a$) but I don't know where to read about ...
5
votes
2answers
98 views

How to solve this recurrence relation $ f(n) = \frac{10+7f(n-1)}{2+f(n-1)}$

I had a problem in which I ended up getting the following recurrence relation: $$\begin{align} &f(1) = 7\\ &f(n) = \dfrac{10+7f(n-1)}{2+f(n-1)} \end{align}$$ I haven't solved much recurrence ...
0
votes
0answers
34 views

Solving a simple delayed differential equation

I have a delayed differential equation of the form $$ x'(t)=\beta-f\left(x\left(\alpha(t)\right)\right) $$ where $\alpha(t)=t_{j}$ for $t\in[t_{j},t_{j+1})$ for $j=0,1,...$, with $t_{0}=0$ and $t_{j+...
1
vote
2answers
36 views

Expected length of 2-coin tossing game until player's ruin

Player $A$ and player $B$ are playing coin tossing game. Player $A$ has $n$ coins, player B has $m$ coins. If two head or tails turn up then player $A$ takes both coins. Otherwise player $B$ takes ...
3
votes
0answers
69 views

Solving a functional equation $2 f(2x)=f(x)(1+\cos(x))+f(x+\pi)(1-\cos(x))$

I am trying to solve the following functional equation, which appears in some of my physics calculations : $f(x)=\frac{1}{2}\left(f(\frac{x}{2})(1+\cos(\frac{x}{2}))+f(\frac{x}{2}+\pi)(1-\cos(\frac{x}...
0
votes
1answer
42 views

Linear recurrent sequences and matrices.

Let $k$ be a field, let $d$ be an integer greater than $1$, let $(v,x)\in k^d\times k^d$ and let $A\in k^{d\times d}$ be invertible. For all $n\in\mathbb{N}$, let define the following element of $k$:...
0
votes
0answers
32 views

Finding a general solution of recurrences

I am unsure how to even start the questions :S I need to learn this stuff for the final exam of my subject and its hard to find a tutorial on how to answer this type of question.
8
votes
0answers
82 views

On the convergence of a more complex iterated radical

After exploring Ramanujan's famed $$3=\sqrt{1+2\sqrt{1+3\sqrt{1+\cdots}}} $$ and $$4=\sqrt{6+2\sqrt{7+3\sqrt{8+\cdots}}},$$ both of which can be expressed more generally by $$x+n+a=\sqrt{ax+(n+a)^2+x\...
0
votes
1answer
21 views

non-homogeneous Recurrence Relation for f(x) = n^2

Im having some trouble with a non-homogeneous Recurrence Relation. My question is: $u_{n} - 5u_{n-1} + 4u_{n-2} = n^2$ My working out so far: $r^{2}-5r+4r = 0$ = (r-1)(r-4) Giving the roots 1 and ...
1
vote
1answer
113 views

How to evaluate or approximate this kind of recursion: $a(n+1) = m \cdot \exp\left(\frac{-K \cdot (m - a(n))}{m}\right),\ n \geq 1$?

Edit: In the original post, I put the function $$a(n+1) = m \cdot \exp(-K \cdot a(n) / m),\ n \geq 2$$ which is not the function I wanted to study. The correct one is the one given below I came up ...
3
votes
3answers
203 views

Is there a general method for solving this type of recurrence?

Edit: Here is the original problem; it is possible that my recurrence for the stationary distribution $\pi$ is incorrect. Consider a single server queue where customers arrive according to a ...
2
votes
4answers
77 views

Recurrence relation $a_r+6a_{r-1}+9a_{r-2}=3$, then find $a_{20}$

Consider the recurrence relation $a_r+6a_{r-1}+9a_{r-2}=3$, given that $a_0=0, a_1=1$. Let $a_{20}=x\times10^9$, then the value of $x$ is______ . My attempt: $a_r=3-6a_{r-1}-9a_{r-2}$ I ...
3
votes
5answers
129 views

Prove upper bound for recurrence

I am working on problem set 8 problem 3 from MIT's Fall 2010 OCW class 6.042J. This is covered in chapter 10 which is about recurrences. Here is the problem: $$A_0 = 2$$ $$A_{n+1} = A_n/2 + 1/A_n, \...
0
votes
1answer
87 views

recursive generating functions

\begin{align} f(0) & = 1 \\ f(1) & = 1 \\ f(2) & = 2 \\ f(2n) & = f(n)+f(n+1), \;\;\;n\gt1 \\ f(2n+1) & = f(n-1)+f(n), \;\;\;n\ge1 \\ \end{align} I am trying to figure out ...
2
votes
1answer
54 views

Solving $nx_n=(n+2)x_{n-1} + 1$ by the telescoping method

I am trying to solve this recurrence relation from a book "Problem solving through Problems" by Loren c. Larson (5.3.14 (b)) using the telescoping method. $$x_0=0\qquad nx_n=(n+2)x_{n-1} + 1\ (n > ...
0
votes
4answers
84 views

Is this recurrence relation $g_{n+1}=ig_n-g_{n-1}$ is a trivial?

Let $g_1=i$ and $g_2=-1$, where $i=\sqrt{-1}$, and $$g_{n+1}=ig_n-g_{n-1}$$ For $n=1,2,3,4, ...$ then $g_n:={i, -1, -2i, 3, 5i, -8, -13i, 21, ...}$ respectively. Is this recurrence relation is ...
1
vote
0answers
19 views

Difference equations and the characteristic polynomial

The context for this is solving the gambler's ruin problem using linear algebra. I haven't found a good explanation for why the linear combination of the eigenvalues for the matrix representing a ...
2
votes
0answers
40 views

$a(n+1, k) = ka(n,k) + a(n,k-1)$

While working a combinatorial problem, I have encountered the recurrence relation $$a(n+1, k) = ka(n,k) + a(n,k-1)$$ where $a(0,0) = 1$ and $a(0,k)=0$ if $k \ne 0$. Except for the $k$ multiplier, ...
0
votes
1answer
14 views

Inequality in recurrence relation

I'm having a mental block understanding what is probably a simple inequality in a guess and check example for a recurrence relation. Would someone please explain to me how they obtain the inequalities ...
1
vote
1answer
32 views

Let t(n) be the number of strings of n letters that can be produced by concatenating copies of the string “a”, “bc”, “cb” find t(3) and t(4)

For each integer n>= 1, let $t_n$ be the number of strings of n letters that can be produced by concatenating (running together) copies of the strings "a", "bc", and "cb" For example, $t_1$ = 1("a" ...
1
vote
0answers
49 views

How can I solve the recurrence [closed]

Solve the recurrence $f(n)=f(\frac{3n}{4})+f(n^{1-b})+cn^b$ where b and c are constants and 0 < b < 1.
2
votes
0answers
94 views

Calculate n-th term of a recursive formula

I have a sequence defined as follows: $a_1 = A$ $a_n = a_{n-1}^2 + B$ $A, B$ are positive integers. I want to design an algorithm, which would calculate $N$-th term of this recurrence modulo $M$ $(...
0
votes
2answers
37 views

Recursive sequence nth element formula

What is the $n$th element of this sequence: $$S_n = S_{n-1} + (c_1 - S_{n-1})c_2$$ where $c_1$ and $c_2$ are constants and $S_1=0$. Thank you,
4
votes
2answers
53 views

Show that the sequence $x_n=\Big[\frac32x_{n+1}\Big]$, $x_1=2$ contains an infinite set of odd numbers and an infinite set of even numbers.

I am having a hard time proving this Let $x_n$ be a sequence such that $x_{n+1}=\Big[\frac32x_n\Big]$ for $n\gt1$, where $[x]$ denotes the nearest integer function and $x_1=2$. Show that ...
0
votes
1answer
27 views

Solving differential equations using series

Suppose $v \in \mathbb{R}$ and $$y\left(x\right)=x^v\left(1+\sum^{\infty}_{n=1}a_nx^n\right)$$ where the series converges for any $x \in \left(-r,r\right), r>0$ If $y\left(x\right)$ is a solution ...
1
vote
0answers
23 views

Frobenius Method

We have been given a Hermite equation $ \frac{d^2 y}{dx^2} -2x \frac{dy}{dx}+2ny=0$ We need to use the Frobenius method to solve. So far we have solved the indicial equation and got r = 0,1 and the ...
0
votes
1answer
45 views

Properties of Bessel Functions

I have shown that the Bessel function $$J_n\left(x\right)=\dfrac{x^n}{2^n}\sum^{\infty}_{n=0}\dfrac{\left(-1\right)^kx^{2k}}{2^{2k}k!\left(n+k\right)!}$$ satisfies the property $$\left(x^{n+1}J_{n+1}...
1
vote
1answer
27 views

Where does this reccurence relation come from?

if$$\alpha_m = \int^{1}_{-1}\cos \pi x (x^2-1)^m dx$$ then how do I get $$\alpha_m = \frac{-1}{\pi^2}(2m(2m-1)\alpha_{m-1} + 4m(m-1)\alpha_{m-2})$$ I have to integrate by parts! But $$\alpha_n = -\...
0
votes
1answer
31 views

Find the Bessel Function solution of the differential equation

For positive n, the ordinary differential equation $$y''+\dfrac{1}{x}y'+\left(1-\dfrac{n^2}{x^2}\right)y=0$$ has as a solution the Bessel function of order n, $J_n\left(x\right)=x^n\sum^{\infty}_{k=...