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

learn more… | top users | synonyms

2
votes
1answer
54 views

Filling of a tank - recurrence relation

Suppose a tank has a maximum limit of 100 units. Each day 2,1 and 0 units are added to the water level with probability p,r and q. Any excess water would overflow and if it reaches the minimum level ...
13
votes
4answers
357 views

Converting recursive equations into matrices

How do we convert recursive equations into matrix forms? For instance, consider this recursive equation(Fibonacci Series): $$F_n = F_{n-1} + F_{n-2}$$ And it comes out to be that the following that ...
3
votes
2answers
62 views

Recurrence Master Theorem Question with asymptotic Upper and Lower Bounds

If I were to solve the recurrence of following equation and give asymptotic upper and lower bounds: $$T(n) = 4T(\frac{n}{2}) + n^2 + n$$ Can I apply Master Theorem on this? My attempt was following: ...
1
vote
1answer
22 views

Queuing theory-Multiple server (reducing simple recurrence formulas)

The equations given in 6.3 have been reduced which really eases the computation in further studies. But I tried to find the method of reducing these but I could not find a way at all. Any hints will ...
2
votes
2answers
66 views

Finding a Closed Form for a Recurrence Relation

I know that a general technique for finding a closed formula for a recurrence relation would be to set them as coefficients of a power series (i.e. a generating function). Then use properties of ...
1
vote
1answer
29 views

non-homogenous recurrence relation, with split boundary conditions

I have non-homogenous recurrence relation: $x_{t+1}=\alpha x_t+\beta x_{t-1}+\gamma$ with the following boundary conditions: $x_2=\alpha x_1+\gamma$ $x_{T}=1/2x_{T-1} +1/2$ Anyone know how to ...
3
votes
1answer
37 views

What's the time complexity of T(n)=nlogn+T(n-1)?

The title says it all. The best I can come up with is that this expands to T(0) + 1log 1 + 2log 2 + ... + (n-1)log (n - 1) + nlog n which is ...
3
votes
1answer
76 views

Limit of a recursiv trigonometric function

So while doing my math homework I recently stumbled upon this little thing: It seems that $y_n = \sin(y_{n-1}) + k$ with arbitrary $y_0$ and $k$ converges to a definite value for $n \to \infty $. ...
0
votes
0answers
44 views

How can I cleverly use the reverse triangle inequality in this case?

Say, we have the following recurrence relation: $$x_{k+2}=4x_{k+1}+x_k(-3-2h\lambda)$$ with $x_0 $ given, $x_1=(1+h\lambda)x_0, h$ small (step size), and $\lambda<0$. Here is the context is case ...
1
vote
1answer
68 views

Fibonacci numbers $F_{n+3} + F_{n} = 2F_{n+2}$

Prove $F_{n+3} + F_{n} = 2F_{n+2}$ for any positive integer n. So What I did was this: fn+ fn+1 = fn+2 fn + fn+1 = fn+2 => fn+2 -fn+1 fn+1 + fn+2 = fn+3 then I subsituted into equation in ...
3
votes
1answer
73 views

Help finding the closed formula for a recurrent relation

In the last steps of finding the complete solution of a linear differential equation by a power series, I got stuck on finding the closed formula for the following recurrent relation: $$B_n = B_{n-1} ...
1
vote
0answers
73 views

Need help with these recurrence relations

I had received some challenging recurrence last week, I did most of them except this and also one of its kind. It states Given $a_0=0$ and $a_1=1$, solve these recurrence relations: ...
3
votes
1answer
107 views

General Solution of Functional Equation

What is the general solution to: $$ \frac{f(x+h)-f(x)}{h} = \frac{1}{x} \tag{1} $$ Obviously the solution to this for the limiting case of $h\to 0$ is $f(x) = \ln(x) + c$ Attempting to solve the ...
1
vote
2answers
39 views

Generating function satisfying a second degree equation

I got this problem in an exercise list: Let $G(x)$ be the generating function of the numeric sequence $(C_n; n \geq 0)$ satisfying the recurrence equation: $$C_n = \sum_{k=0}^{n-1}C_kC_{n-k-1}, ...
0
votes
1answer
41 views

Limit of recurrence relation $x_k= f(x_{k-1})$ for an increasing function $f:[0,1]\to[0,1]$

Is there a standard result out there that gives the following? It looks graphically like it must be true, but I'd like to appeal to a known result if possible. Let $f:[0,1]\to[0,1]$ be a continuous, ...
2
votes
1answer
71 views

Quadradic recurrence relation

There is an method to solve recurrences of the form $a_{n+1} = (a_n + c)^2$? I am particularly interested when $c = 1$. I tried to use generating functions but I got stuck with. Let $G(x) = \sum_{k ...
3
votes
1answer
87 views

Solving a recurrence relation ${}$

I feel I'm wasting my time trying to solve this $a_0$ is given $\displaystyle a_{n+1}=\frac{n-1}{n+2}(a_n-n-2)$ Mathematica found a closed form but there's a problem when evaluating for ...
3
votes
2answers
104 views

Determinant involving recurrence

Evaluate $$\left| A \right| = \left| {\matrix{ {x + y} & {xy} & 0 & \cdots & \cdots & 0 \cr 1 & {x + y} & {xy} & \cdots & \cdots & 0 \cr 0 ...
1
vote
1answer
72 views

Divide and Conquer (recurrence relation problem)…

The problem: (a) Use a divide-and-conquer approach to devise a procedure to find the largest and next-to-largest numbers in a set of n distinct integers. (b) Give a recurrence relation for ...
0
votes
1answer
26 views

Change of variables in function $T(n)$.

I've been given this recurrence to solve: $T(n) = T(\sqrt n) + \theta(lglgn)$ And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows: $S(m) = ...
6
votes
1answer
125 views

Limit related to the recursion $a_{n+1}=(1-n^{-1/4}a_n)a_n$

Let $0<a_{1}<1$, with $$a_{n+1}=a_{n}(1-n^{-\frac{1}{4}}a_{n})$$ Does there a real numbers $A$ which make the limit $$ ...
0
votes
3answers
48 views

Recurrence relations for students of the third year of secondary school.

I am not able to solve this problem in order to find a explicit form for the recurrence relation (note: in the original text I can read "a with n" and "a with n-1", but I am not able to format here) ...
2
votes
2answers
92 views

How to solve the recurrence $T(n) = T(n-1) +\sqrt{n}$?

While solving the recurrence of the title I come to the series $$T(n) = \sqrt1 + \sqrt2 + \sqrt{3} + \cdots + \sqrt n.$$ Please somebody help me how to solve this.
0
votes
0answers
67 views

Partial Derivative of Integration

Suppose that I have some set of weight functions, $W = \{w_1(i,j), w_2(i,j),..., w_k(i,j)\}$, where each weight function is a Taylor polynomial in $\mathbb{R}^2$ with constants $c_{kn}$ where $n$ is ...
6
votes
2answers
90 views

Is the sequence $x_{n+1} = \frac{x_n + \alpha}{x_n + 1}$ convergent?

Fix $\alpha > 1$, and consider the sequence $(x_n)_n \geq 0$ defined by $x_0 > \sqrt \alpha$ and $$x_{n+1} = \frac{x_n + \alpha}{x_n + 1}, n = 0, 1, 2, \dots$$ Does this sequence converge, ...
0
votes
0answers
33 views

Did I obtain this recursion in the Fourier domain correctly?

I would like to calculate the following recursion: $$f_n(x)=\int_{B}^{A}f_{n-1}(x-\omega)f(\omega)\mbox{d}\omega\quad\quad f_1(\omega):=f(\omega)$$ This is simply the convolution of $f$ with itself ...
0
votes
1answer
29 views

Solve the recurrence relation

Assuming that $n$ is a power of $2$, solve the recurrence relation $$T(n)=2T\left(\frac{n}{2}\right)+2$$ Take $T(2)=1$ and $T(1)=0$. Also how can this be done with the master theorem, if possible?
-4
votes
1answer
46 views

A recurrence involving nested cube roots [closed]

Solve the equatation $\sqrt[3]{x\sqrt[3]{x\sqrt[3]{x\sqrt[3]...}}} = 3$ Only have variant: 4 9 16 3
0
votes
2answers
27 views

Find the values of $r_1, r_2, r_3$ in the recurrence relation $a_n = r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $

Consider the recurrence relation $a_n = > r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $ for $n \ge 3$. The roots of the characteristic polynomial are $x = -1$ of multiplicity 2, $x= 3$ of ...
0
votes
1answer
32 views

How $L_n = L_{n-1} + n $ become $L_{n-2} + (n-1) +n $ and So on?

I am currently reading 'concrete mathematics' of knuth. I don't know how $L_n = L_{n-1} + n $ become $L_{n-2} + (n-1) +n $ and finally $L_0+1+2...+(n-2)+(n-1)+n $ can you please tell me?
0
votes
1answer
10 views

Solve linear homogeneous recurrent relation with constant coef using generating functions

I have the following linear homogeneous recurrent relation which I have to solve using generating functions. $a_{n+2}-2a_{n+1}-3a_n = 0$ The generating function for this is: ...
0
votes
1answer
26 views

Recurrence relation task

Can someone explain me this: $T(n)=-T(n-1)+2\times T(n-2)+3 \times 2^n+n$ According to Wolfram Alpha the answer is: $$ T(n) = c_1(-2)^n + c_2 + \dfrac{1}{18}n(3n + 7) + 3 \times 2^n - ...
1
vote
1answer
36 views

Binary string block recurrence

Let $a_n$ be the total number of blocks for all $2^n$ binary strings with length $n$. Prove the following recurrence: \begin{equation*} a_n = 2a_{n-1} + \frac{2^{n}}{2} \end{equation*} For example ...
0
votes
2answers
44 views

Complexity of $T(n) = 2T(n/2) + n$

How can I prove that $T(n) = 2T(n/2) + n$ is $\mathcal{O}(n \, \log{n})$ without master theorem , if $T(1)=\mathcal{O}(1)$? How can I continue from here? $T(n) = 2T(n/2) + n,$$T(n) = 4T(n/4) + ...
1
vote
1answer
21 views

Cardinality of a set with a recurrence relation.

Let $A = \left\{ f\in \mathbb{N}\rightarrow \mathbb{C} \mid \forall n\in \mathbb{N}. f(n+3) + 3f(n+1) = f(n+2)+f(n) \right\}$ What is $\left|A\right|$? Well, I tried to treat $f$ as a recurrence ...
5
votes
2answers
371 views

Series of sequence converges?

Given the recursively defined sequence $$ a_2 = 2(C+1)a_0 $$ and $$ a_{n+2}=\frac{\left(n(n+6)+4(C+1)\right)a_n - 8(n-2)a_{n-2}}{(n+1)(n+2)}. $$ that I got from the Frobenius method applied to an ODE, ...
2
votes
2answers
92 views

Calculate f(n+1)-f(n-1) based on f(n)???

Being: $$f(n) = \left(\frac{5+3\sqrt5}{10}\right)\cdot\left(\frac{1+\sqrt5}{2}\right)^n+\left(\frac{5-3\sqrt5}{10}\right)\cdot\left(\frac{1-\sqrt5}{2}\right)^n$$ Calculate: $$f(n+1)-f(n-1)\\ ...
2
votes
1answer
24 views

Uniqueness of solutions to linear recurrence relations

I understand that if I have a linear homogeneous recurrence relation of the form $q_n = c_1 q_{n-1} + c_2 q_{n-2} + \cdots + c_d q_{n-d}$, I can construct the characteristic polynomial $p(t) = t^d - ...
3
votes
2answers
56 views

Solving combinatorical problem using characteristic polynomial

How many $6$ length strings above $\left\{1,2,3,4\right\}$ are there such that $24$ and $42$ aren't allowed. The suitable recurrence relation for this problem is: $a_{n+2} = 2a_{n-1} + ...
1
vote
2answers
29 views

Finding the inhomogeneous solution

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would I find the inhomogeneous solution for this since the homogenous solution is 0 given initial conditions?
1
vote
2answers
45 views
0
votes
0answers
14 views

Compact closed form for linear recurrence formulas

Assume you have some linear recursion formula $$f(\vec x)=\sum_{\vec y\in Y}w_{\vec y}f(\vec x - \vec y)$$ Where $\vec y\geq 0 $ and $||\vec y||>0$, $w_{\vec y}\in\mathbb{R}$ and $\vec x , \vec ...
0
votes
2answers
36 views

Help solving recursive relations

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would you solve this recursive relation? I have the homogenous solution, but am having issues with the ...
0
votes
3answers
50 views

Differentiate a recurrence relation

How do I calculate the derivative of an equation like: $z_n = (z_{n-1} + c)^2$ with respect to $n$ where $z_0 = 0$ and $z,c \in \mathbb{C}$ I suspect that, for a given $z$, the derivative is not ...
1
vote
1answer
61 views

Concerning a specific family of recursive sequences

There is a family of recursive sequences that I came up with: $$a_n=\text{sum of factors less than $a_{n-1}$ of } a_{n-1}, a_0\in\mathbb{N}$$ First question: Has it been studied before? Here are ...
0
votes
3answers
62 views

Are Pell solutions “unique”??

Given the Pell equation $$X^2-2Y^2=1$$ and two solutions $(x_j,2uv)$ and $(x_k,2ac)$, with $uv=ac$ and $\gcd(u,v)=\gcd(a,c)=1$ and $u>v$ and $c>a$. Can one prove that $(u,v)=(c,a)$, and hence ...
3
votes
2answers
72 views

Find the limit of the sequence given by recurrence relation

Find the limit of the sequence given by recurrence relation $c_{n+1} = (1-\frac{1}{n})c_n + \beta_n $ where $ \beta_n $ is any sequence with the property $n^2\beta_n \to 0$ as $ n \to \infty$ I've ...
2
votes
1answer
102 views

How can I make this recurrent equation non-recurrent?

I have a recurrent equation that defines a sequence $a_k$ from a sequence $b_k$: $$a_k = b_k - \sum^\infty_{i=k+1}a_i$$ How can I write this equation without mentioning $a_k$ on the right side?
0
votes
0answers
61 views

Recurrence equation analysis of the form T(x) = t + max{T(…) + …}

I want to find the worst-case running time of an algorithm I came up with, which follows the following recurrence equation: The worst-case running time is $\Theta(n^2) + T(n, 2, n)$, where $$ ...
1
vote
0answers
25 views

What [precisely] is special, algebraically, about fundamental Pell solutions?

I'm asking for a list of algebraic identities which "uniquely identify" (or nearly so) the fundamental solution (or those immediately around it) of a Pell equation. As a concrete [numerical] example, ...