Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [recurrence-relations]

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

0
votes
0answers
18 views

Complexity of $T(n) = T(\frac{4}{7}n + 1) + T(\frac{3}{7}n+1) + \log n$

How is Complexity time of this recurrence ? I tried with the tree method and I have $O(\log^2(N))$
-1
votes
0answers
20 views
0
votes
0answers
15 views

Equilibrium points of the two-dimensional difference equation model

I am given the following two difference equations and asked to find the equilibrium points, I've looked on many online notes; however, I could not find anything that was similar to my problem, any ...
-1
votes
1answer
52 views

Prove that \[(x^{2} +xy -y^{2})^{2}=1\] has consecutive Fibonacci numbers as solution

Apologies if it's a duplicate question. I was not able to find such question though. I don't know how to proceed on this.
1
vote
3answers
33 views

Convert recurrent formula with polynomial term / parameter to explicit formula

So, I know how to convert to explicit formulas things like the Fibonacci sequence cause it only consists of $a_n$ like this: $$a_{n} = a_{n-1} + a_{n-2}$$ However my problem is I've encountered a ...
0
votes
1answer
24 views

Find $a_{n+2}+3a_{n+1}+2a_n=3^n$ if $a_0=0$ and $a_1=1$, and prove

Find $a_{n+2}+3a_{n+1}+2a_n=3^n$ if $a_0=0$ and $a_1=1$, and prove the result. What I have done: First we have to find the homogeneous recurrence relation solution, so $$a_{n+2}+3a_{n+1}+2a_n=0\...
1
vote
1answer
35 views

Using the substitution method on $p(n)=\sqrt{n}p(\sqrt{n})+\sqrt{n}$ [duplicate]

My task at hand is to find a tight asymptotic upper bound for the recurrence $p(n)=\sqrt{n}p(\sqrt{n})+\sqrt{n}$. My initial idea has been to substitute $m=\lg n$ and define a new recurrence $s(m)=p(2^...
2
votes
1answer
63 views

I didn't understand this recurrence relation solution.

Recently, i was trying to solve this recurrence relation $$ a_{n+4} = \frac{-\alpha(x)}{(n+4)} \cdot a_{n+3} +\frac{-\beta(x)}{(n+3)\cdot (n+4)} \cdot a_{n+2} $$ But i can't solve for $a_n$ I've ...
1
vote
0answers
22 views

Linear convergence of sequence

I have the following exercise but it seems to me that this is false : Let $(x_n)_{n \in \mathbb{N}}$ by a sequence of real numbers and $x^* \in \mathbb{R}$. We say that the sequence $(x_n)$ ...
0
votes
0answers
8 views

Expected iterations of finding a non-repetitive sequence

I am working on problem 8 in chapter 5 of The Probabilistic Method and I couldn't solve the second half of it. Problem: For every $n\ge1$ and every sequence of lists of symbols $L_1,L_2,..., L_n$, ...
5
votes
1answer
63 views

Finding the closed form for $x_n^2 = -x_{n-1}^2+6x_{n-2}^2+n$

I'm trying to find a closed form for the recurrence relation $x_n^2 = -x_{n-1}^2+6x_{n-2}^2+n$, with $x_1 = \frac{1}{4}, x_2=\frac{\sqrt{13}}{4}$ and $x_i \in \mathbb R^+$. My attempt was to let $z_n=...
0
votes
3answers
28 views

Proof by Induction help (inequality)

I need to prove if, $$a_1=1,\ a_2=2$$ and $$a_n=2a_{n-1}+a_{n-2}$$ then $$a_n\leq \left(\frac{5}{2} \right)^{n-1}$$ Proof (by using strong induction): As far as I go, is that I prove both bases ...
3
votes
1answer
96 views

Prove that $\lfloor n\sqrt{2}\rfloor $ doesn't satisfy any linear recurrence with constant coefficients.

Prove that $\lfloor n\sqrt{2}\rfloor $ doesn't satisfy any linear recurrence with constant coefficients. Using one of the formula for floor function, we can write: $$ \lfloor n\sqrt{2}\rfloor =\frac{-...
1
vote
1answer
26 views

Homogeneous linear difference equation with multiple roots

Given a homogeneous linear difference equation $$\sum_{j=0}^k \alpha_j y_{n+j} = 0$$ I want to show that if $r$ is a root of the characteristic polynomial $$\rho(\xi) = \sum_{j=0}^k \alpha_j \xi^j$$ ...
2
votes
1answer
54 views

Reduction Formulae Integral $x(1-x^3)$

The question asks us: "If $$u_n=\int_0^1x(1-x^3)^ndx$$ show that $$u_n= \frac {3n}{3n+2}u_{n-1}$$ I've tried integration by parts using a coefficient of $1, x$ and even tried reducing the $...
0
votes
2answers
45 views

Find generating function of $ a_n=2a_{n-1}-3a_{n-2}+4n-1 $

I have to find generating function of $ a_n=2a_{n-1}-3a_{n-2}+4n-1 $ where $a_0=1$ and $a_1=3$. I'm currently stuck at the form: $f(x) = \sum_{n=0}^\infty a_nx^n = 1 + 3x +2x\sum_{n=2}^\infty(a_{n-1}...
0
votes
1answer
26 views

Matrix for recurrence relation

I have recurrence relation for which i need to figure out matrix which can used for matrix exponentiation. $f(n) = f(n-1) + f(n-3)$ Which I think can be written as $f(n) = a f(n-1) + b f(n-2) + c f(...
2
votes
2answers
54 views

$T(n) = T(\sqrt{n}) + \sqrt{n}$ solving recurrence

$T(n) = T(\sqrt{n}) + \sqrt{n}$ I would like to try solving this recurrence in big-O/$\Theta$/$\Omega$. My first idea was to take $n = 2^m$ so: $$T(2^m) = T(2^{m/2}) + 2^{m/2}$$ Which we rewrite as: ...
1
vote
0answers
19 views

Recursion ceiling and radicals of integers

Given $n,k\in\mathbb Z$ what is the minimum $r$ needed such that following iteration is $\leq2$? $$n_0=n$$ $$n_1=\lceil n_0^{1/k}\rceil$$ $$\vdots$$ $$n_{i+1}=\lceil n_i^{1/k}\rceil$$ $$\vdots$$ $$...
2
votes
5answers
61 views

Study convergence of $x_{n+1} = \frac{1}{2x_n - 1}$ when $x_1 = {9\over 10}$

Given a recurrence relation $$ x_{n+1} = \frac{1}{2x_n - 1}\\ x_1 = {9\over 10}\\ n\in\Bbb N $$ Figure out whether the sequence converges and find $\lim x_n$ in case it exists. I've started with ...
0
votes
1answer
35 views

Solving for n = 4 in recurrence relation

I am going through 'Concrete Mathematics' by Knuth et al. There is a question that asks one to find the closed form for a recurrence relation defined as follows: $$ Q_{0} = \alpha; \\ Q_{1} = \beta; \...
1
vote
2answers
31 views

Solving Recurrence Relation Using Substitution/Geometric Series

$$ T(n) =4T(\frac{n}{2})+ n^\frac{5}{2} $$ I'm having trouble solving this recurrence relation above to identify the time complexity below by using substitution/plugging. I'm able to do it using ...
0
votes
1answer
15 views

how do I solve this recursive formula: T(1) = 1 and T(n - 1) + 3

Im not sure im doing this correctly but it seems that I am getting this T(1) = 1 T(2) = T(2-1) + 3 = T(1) + 3 = 1 + 3 T(3) = T(3-1) + 3 = T(2) + 3 = 1 + 3 + 3 T(4) = T(4-1) + 3 = T(3) + 3 = 1 + 3 +...
3
votes
2answers
83 views

Study convergence of $x_{n+1} = a\left(x_n + {1\over x_n}\right)$, for $x_1 = a$ and $a \in (0, 1)$

Given a recurrence relation: $$ x_{n+1} = a\left(x_n + {1\over x_n}\right) \\ x_1 = a\\ n\in\Bbb N $$ Show that: $$ \begin{align*} a \ge 1 &\implies \lim_{n\to\infty} x_n =+\infty \tag1\\ a \...
1
vote
1answer
35 views

Efficient method for computing the product of the first 8 terms of a recursive sequence

The problem I am trying to solve is the following: Let $x_1=97,$ and for $n>1,$ define $x_n=\frac{n}{x_{n-1}}.$ Calculate $x_1x_2 \cdots x_8.$ I tried the painstaking fail safe method for the ...
0
votes
0answers
18 views

How to find closed-form formula of $b_n = \sum_{j+k=n} a_{j,k}$

I’ve tried to use generating functions (GF) on this ‘convolution’-looking type of recurrence relation to find a closed-form formula for $b_n$ $$ b_n = \sum_{j+k=n} a_{j,k} $$ But any definition of ...
2
votes
0answers
58 views

Prove a limit exists and find it if $x_{n+1} = 1- {1\over 4x_n}$, where $x_1 = a$ and range of $a$ is given.

Given a recurrence relation: $$ x_{n+1} = 1- {1\over 4x_n} \\ x_1 = a \in\Bbb R \\ n\in\Bbb N $$ Prove that the limit exists and evaluate: $$ \lim_{n\to\infty}x_n $$ given $a$: $$ \begin{...
5
votes
2answers
117 views

How to solve this recurrence relation using generating functions: $a_n = 10 a_{n-1}-25 a_{n-2} + 5^n\binom{n+2}2$?

How can we solve the following recurrence relation using GF? $a_n = 10 a_{n-1}-25 a_{n-2} + 5^n {n+2 \choose 2}$ , for each $n>2, a_0 = 1, a_1 = 15$ I think that most of it is pretty ...
0
votes
0answers
26 views

Finding length of LFSR (linear feedback shift register) period and the values of its coefficients.

I have been presented with the following problem: The following sequence was generated by a linear feedback shift register. Determine the recurrence that generated it. $1,0,1,0,0,1,1,0,0,1,0,0,0,...
1
vote
1answer
52 views

Series Solution to the ODE $y''+2y'+y=0$

here's where I'm at, The ode we are trying to solve is, $$y''+2y'+y=0$$ I know this solution is of the form: $$\sum_{n=0}^{\infty}a_nx^n $$ And from that we get the following $$\sum_{n=0}^{\infty}(n)(...
4
votes
2answers
53 views

Proving the values obtained by a recurrence relation are always perfect squares? [duplicate]

A problem appeared in a maths contest as follows: Consider a recurrence relation: $$a_{n+3}= - a_{n+2}+2a_{n+1}+ 8a_{n}$$ where the intial conditions are : $a_1=1;a_2=1;a_3=9$. Then prove that the ...
1
vote
2answers
37 views

Power series solution to $y’ + 2xy = 0$

So I'm stuck. I'm pretty sure the constant $c_1$ equals zero, which makes the equation easy to solve by using the identity principle. But how do I show that $c_1=0$.
3
votes
1answer
52 views

Sum of Sine and Cosine to Higher Powers Is Constant (Recursion, Proofs)

I have observed this empirically, but I have no idea how to prove it or if it has been proven before. If this has been proven before, in any form, either more or less generic, please point me to such ...
0
votes
0answers
39 views

Proof by Induction of a recurrence relation

I am stuck with following proof which I am not able to get. One such code is a list of $2n$ $n$-bit strings in which each string (except the first) differs from the previous one in exactly one bit. ...
2
votes
1answer
34 views

Finding solution of recurrence relations $T(n) = 2T(n/3)+n$

Evaluate: $$T(n)=2T(n/3)+n$$ $$T(n/3)=2T(n/9)+n/3$$ $$T(n/9)=2T(n/27)+n/9$$ Substitute the following result: $$T(n)=2(2(2T(n/27)+n/9)+n/3)+n$$ $$T(k)=2^k T(n/3^k)+n/3^{k-1}+n/3^{k-2}+....+n/3^...
0
votes
2answers
14 views

How to translate from a 2x2 state-space difference equation to a 2nd-order difference equation

I have a state-space evolution equation of the form $$\begin{bmatrix}u_k\cr v_k\end{bmatrix} = \begin{bmatrix}1-a & c \cr b(a-1) & 1-bc\end{bmatrix} \begin{bmatrix}u_{k-1}\cr v_{k-1}\end{...
6
votes
1answer
55 views

Study convergence of $x_{n+1} = x_n^2 + 3x_n + 1$, where $x_1 = a$, and $a$ takes different values and find its limit.

Given a recurrence relation: $$ x_{n+1} = x_n^2 + 3x_n + 1 \\ x_1 = a\\ n\in\Bbb N $$ Figure out whether this sequence has a limit (either finite or infinite) and find it for: $$ \begin{align*} ...
2
votes
2answers
77 views

Rigorous or not?

I want to prove $$T(n,k)=\frac{n}{\left\lfloor\frac{n+k+1}{2}\right\rfloor}(T(n-1,k)+T(n-1,k-1))=\binom{n}{k}\binom{n-k}{\left\lfloor\frac{n-k}{2}\right\rfloor}$$ First we know only that $$T(n,k)=0, n&...
4
votes
2answers
61 views

Freaky Polynomial: $P_n(x)=\left(x\frac{d}{dx}\right)^n f(x)$

I am investigating the polynomial $$P_n(x)=\left(x\frac{d}{dx}\right)^n f(x)=xP_{n-1}'(x)$$ for some known function $f$. I defined $f_n(x)=\frac{d}{dx}f_{n-1}(x)$ with $P_0=f_0=f$. And I also defined ...
0
votes
1answer
50 views

Competition algorithm

$n$ athletes ($a_1,...,a_n$) are arranged in a line. At each time $t$, two adjacent athletes race each other. The loser is removed from the line and the winner stays in the same position. This ...
0
votes
2answers
39 views

recurrence relation limit $x_{n+2}=(a+b)\cdot x_{n+1}-ab\cdot x_{n}$

Let $0<b<a$ and $(x_{n})_{n\in \mathbb{N}}$ with $x_{0}=1, \ x_{1}=a+b$ $$x_{n+2}=(a+b)\cdot x_{n+1}-ab\cdot x_{n}$$ a) If $0<b<a$ and $L=\lim_{n\rightarrow \infty }\frac{x_{n+1}}{x_{n}}$ ...
2
votes
2answers
38 views

Recurrence $5f(n-1)-8f(n-2) + 4f(n-3)$ with $f(0) = -1$, $f(1) = 1$ and $f(2) = 7$

In our combinatorics script it is written that the recurrence $$f(n) = 5f(n-1)-8f(n-2) + 4f(n-3) $$ can be solved with the initial values $f(0) = -1$, $f(1) = 1$ and $f(2) = 7$ I don't know how to ...
4
votes
1answer
84 views

On a mistake in a derivation regarding a recurrence relation.

Suppose we have a sequence $\{u_t \}_{t \in \mathbb{N}}$ given by the recurrence relation $$u_{t+1} = q_0 u_t + q_1 u_{t-1} + \dots + q_p u_{t-p} + \epsilon, \quad \epsilon >0$$ where $p \in \...
0
votes
1answer
25 views

Recurrence relation for tiling

You need to tile an $n \times 1$ hallway with unlimited supply of $1 \times 1$ red tiles, $2 \times 1$ red tiles, and $2 \times 1$ blue tiles. Write down the recurrence relation formula and initial ...
0
votes
3answers
39 views

How to prove $a_1 = 2$, $a_2 = 4$ and $a_{n+1} = \frac{1}{3}(2a_n+a_{n-1})$ for all $n \geq2$

Let $a_1 = 3$, $a_2 = 4$ and $a_{n+1} = \frac{1}{3}(2a_n+a_{n-1})$ for all $n \geq2$ Prove that for all positive integers $n$, $3 \leq a_n \leq4$ This was a practice problem in my textbook in the ...
0
votes
0answers
23 views

Verification (and help) with the questions related to convergence of recurrences in the form $x_{n+2} = kx_{n+1} + px_n$

Given $x_1 = a$ and $x_2 = b$ find the values of $a, b \in \Bbb R, n\in\Bbb N$ for which the following recurrences converge (diverge): $$ \begin{align*} x_{n+2} &= 2x_{n+1} - x_n \tag1\\ x_{n+2} ...
0
votes
0answers
16 views

5-term to 3-term recurrence relation

I have a 5-term recurrence relation of the form: $$\alpha_n a_{n-3} + \beta_n a_{n-2} + \gamma_n a_{n-1} + \delta_n a_{n} + \rho_n a_{n+1} =0 .$$ How can I rewrite this, as a 3-term recurrence ...
2
votes
1answer
105 views

Show convergence of $x_{n+1} = x_n(a-x_n)$ for $n\in \Bbb N$.

Let $x_n$ denote a sequence given by a recurrence relation: $$ x_{n+1} = x_n(a-x_n)\\ 0 < x_1 <a\\ n\in\Bbb N $$ Show that: $$ \begin{align} a > 1 &\implies \lim_{n\to\infty}x_n =...
0
votes
0answers
83 views

Where is the mistake in my approach?

I did a little research for the question I asked before. Let $f:\mathbb{R}\rightarrow \mathbb{R}$ , $f(x)=\frac{ax+b}{cx+d}$ and $a,b,c,d>0$ then $f^1(x)=f(x), f^2(x)=f(f(x)), f^3(x)=f(f(f(x))...
4
votes
1answer
49 views

Proof by induction: $a_n > n + \frac{1}{3} \space \forall n \in N,\space n\geq 4$

How do I prove this by induction? Let $(a_n)_{n\in N}$ be the sequence defined by: $$a_1=1,\space a_2=\frac{3}{2},\space a_{n+2}=a_{n+1}+\frac{2n+1}{n+2}a_n \space \space (n\in N)$$ Prove that $...