# Questions tagged [recurrence-relations]

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

6,774 questions
Filter by
Sorted by
Tagged with
39 views

### How to find a non-recursive formula for a recursively defined sequence

Given: $\mu(0)=0$ $\mu(i)= 2\mu(i-1) + 2^{i-1} \ \ \ \ \ \ \forall i \in N$ I would like to know if there is any way of obtaining the non recursive formula for $\mu (i)$: $\mu(i) = i2^{i-1}$ ...
31 views

### calculating total number of allowable paths

I seem to be struggling with the following type of path questions Consider paths starting at $(0, 0)$ with allowable steps (i) from $(x,y)$ to $(x+1,y+2)$, (ii) from $(x,y)$ to $(x+2,y+1)$, (iii)...
55 views

### Rumor has it in Canada that needs to be solved… [closed]

A rumour is being spread by students in Canada. At the start of day $1$, a set of $10$ people know the rumour. Let $S_0$ be this set of people, and for $n \geq 1$, let $S_n$ denote the set of people ...
22 views

### finding formula for generating function for recurrence relation

I need to solve the recurrence relation $$A_n=2A_{n-1}+A_{n-2}$$ with $A(t)=\sum_{n=0}^\infty A_n t^n$ and initial conditions $A_0 = 1$ and $A_1=2$. I am trying to find the generating function ...
18 views

### Solving recurence equations - reference request

I have to solve several recurrence equations originating from physical problems, and I am looking for some references where techniques for different types of equations are collected. Most of my ...
22 views

### Trial solution for in-homogenous differential equation with complex numbers

I am trying to solve following: Given is the differential equation $y^{(4)} + 4y'' + 16y = b(x)$ with the solutions $z_{1,2}=±2i$. Now I have to find trial solutions for the particular solutions, ...
34 views

26 views

### Prove that in a recurrence relation a_n+2 = a_n+1 + a_n , m | n if and only if a_m | a_n [closed]

I came up with this problem in a Problem Set on Recurrence Relations : Prove that in a recurrence relation a_n+2 = a_n+1 + a-n , m |n if and only if a_m | a_n I can understand this is a fibonacci ...
18 views

### Validity of Proof that Recursive Function is Increasing

I have a recursive function defined as follows, $$a_{1}=1,a_{k+1}=\sqrt{2a_{k}+3} \: \forall k\in \mathbb{N}$$ I think I found a very quick way to demonstrate that the function is increasing, but ...
70 views

### Convergence of a recurrent sequence

Sorry if this was already proved (that sequence converges to $\pi$) but I cannot find that proof. So recurrent sequence is : $$a_{n+1}=a_{n}+\sin(a_n)$$ and it seems if $0 < a_0 < 2\pi$ it ...
33 views

### For constants $a$ and $b$, the general solution of the recurrence relation $a_n = 4a_{n-1}+12a_{n-2}$ is…? [closed]

For constants $a$ and $b$, the general solution of the recurrence relation $$a_n = 4a_{n-1}+12a_{n-2}$$ is...?
15 views

### Reference stability/convergence of nonlinear recurrence relations using analytical methods

Example of a problem Let’s say we have the recurrence relation : $$x_{n+1}=\frac{2}{3}(2x_n -x_n^2).$$ We can easily find its fixed points, namely $x=0$ and $x=1/2$. I have found numerically that ...
11 views

### Limit of Recursive Function (Methodology)

Goal: Find $$\lim_{n \rightarrow \infty} d_{n+1}^2$$ where $$d_{n+1}^2 = d_n^2 + r^2 - 2 \cdot r \cdot d_n \cdot \cos \theta$$ for constant $r$ and $\theta < \frac{\pi}{2}$. Attempt: \begin{...
33 views

### Recurrence relation proof

Let $\alpha$ be a positive integer. Let $b_n$, $n=1, 2, 3 \ldots$ be the sequence given by the recurrence relation $b_{n+2}=2\alpha^2b_{n+1}-\alpha^4 b_{n}$, $n=1, 2, 3 \ldots$ with initial ...
63 views

### solution to recurrence relation $a_{n+2}=-2 a_{n+1}+8 a_n+4n^2$

Find the solution for the below recurrence relation with initial conditions $a_1=10$, $a_2=31$ $$a_{n+2}=-2 a_{n+1}+8 a_n+4n^2\,.$$ Let us first consider the corresponding homogeneous recurrence ...
12 views

### Question about Expected Values for a probabilistic recurrence relation

Let $Q(x)$ be such that $$Q(x) = \begin{cases} Q(x - 1) + 1 & \text{w.p.} \ \ 0.5 \\ 0.5Q(x - 1) & \text{w.p.} \ \ 0.5 \\ \end{cases}$$ with $Q(1) = 1$. What is the expected value of $Q(n)$ ...
20 views

27 views

### Generating Function of Integer Partitions

Let $p_{k}(n)$ be a number of partitions of $n$ that into parts not greater than $k$. $p_{k}(n)=p_{k-1}(n)+p_{k}(n-k)$ i will prove this partition recurrence bu using Generating Functions of ...
Given $F(n)=a\cdot F(n-1)-b$ ,$n$ even $F(n)=a\cdot F(n-1)+b$ ,$n$ odd $F(0),a,b$ are constants. How to calculate $n$-th term in $log(n)$ time? I learnt matrix exponentiation technique. But ...