Articles of recurrence relations

Closed Form of Recurrence Relation

I have a recurrence relation defined as: $$f(k)=\frac{[f(k-1)]^2}{f(k-2)}$$ Wolfram Alpha shows that the closed form for this relation is: $$ f(k)=\exp{(c_2k+c_1)} $$ I’m not really sure how to go about finding this solution (it’s been a few years…). Hints?

recursion relation for sequence of random variables

Let $\dots, \xi(-1),\xi(0),\xi(1),\dots$ be a sequence of i.i.d. random variables on $\mathbb Z$ with $\mathbb E[\xi(n)]=0, \mathbb E[\xi(n)^2]=1$. The process $(X(n))_{n\in \mathbb Z}$ is recursively defined by $$X(n+1) = \frac{1}{2}X(n) + \xi(n)$$ What is an explicit process $X(n)$ that fulfills this relation? For whatever I do, I need an initial condition for the recursion relation, […]

recurrence relation concrete way to solve it

I have the following recurrence relation: $$a_n = 2a_{n-1} + 2^n; a_0 = 0$$ I used the characteristic equation method and some method I found online by calculating the $n+1$ th term and subtracting accordingly the equation with $a_{n+1}$ minus the equation with $a_{n}$: $$a_{n+1} = 2a_n + 2^{n+1} \\ a_{n+1} – 2a_n = 2a_n […]

Number of ways of walking up $6$ steps taking $1, 2,$ or $3$ at a time, and a recurrence relation

Suppose you want to walk up a staircase of $6$ steps, and can take $1, 2$ or $3$ steps at a time. How many ways are there to walk the $6$ steps? It seems hard to count the number of ways of walking the steps directly, but on second thought we can find a relation […]

Prob. 18, Chap. 3 in Baby Rudin: Behaviour of $x_{n+1}=\frac{p-1}{p} x_n+\frac{\alpha}{p} x_n^{1-p}$ with $\alpha>0$ and $p$ a positive integer

This is Prob. 18, Chap. 3 in Baby Rudin. Let $\alpha$ be a given positive real number, and let $p$ be a given positive integer. For an arbitrary choice of $x_1 > 0$, let’s define for every $n\ge1$, $$x_{n+1} = \frac{p-1}{p} x_n + \frac{\alpha}{p} x_n^{-p+1} $$ For $p = 2$ and $x_1 > \sqrt{\alpha}$, this […]

What are some strategies for creating linear recurrence relationships?

For instance if I have a string of numbers outputted from some function $f(1), f(2), f(3), \ldots, f(n)$ that can be expressed in the form of $f(n) = af(n-10) + bf(n-9) + \cdots+ jf(n-1)$ etc (It doesn’t have to be $n-10$, just using it as an example), how do you go about deriving such an […]

A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1s.

A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1s. (A binary sequence only uses the numbers 0 and 1 for those who don’t know) B) Repeat for n-digit ternary sequences. (only uses numbers 0, 1, and 2) C) Repeat for n-digit ternary sequences with no consecutive […]

Solving recurrences of the form $T(n) = aT(n/a) + \Theta(n \log_2 a)$

The time complexity for the merge sort algorithm is $T(n) = 2T(n/2)+\Theta(n)$, and the solution to this recurrence is $\Theta(n\lg n)$. However; assume you are not dividing the array in half for sorting, but instead in, say, $a$ pieces. Then the time would be something like $T(n) = aT(n/a) + \Theta(n \log_2 a)$. (The last […]

About the positive sequence $a_{n+2} = \sqrt{a_{n+1}} + \sqrt{a_n}$

Given the positive sequence $a_{n+2} = \sqrt{a_{n+1}}+ \sqrt{a_n}$, I want to prove these. 1) $|a_{n+2}| > 1 $ for sufficiently large $n \ge N$. 2) Let $b_{n} = |a_{n} – 4|$. Show that $b_{n+2} < (b_{n+1} + b_{n})/3$ for $n \ge N$. 3) Prove that the sequence converges. How should I proceed? Is there a […]

Representing affine transform of Legendre polynomials

I have a function defined as a set of weighted Legendre polynomials: $f(x)=\alpha_0 P_0(x) + \alpha_1 P_1(x) + \alpha_2 P_2(x) +\ldots$. I have another function similarly defined with Legendre basis weights, but it’s over a different range. I want to compare the two functions over the range where they overlap. This means I need to […]