# Questions tagged [recurrence-relations]

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

8,797 questions
Filter by
Sorted by
Tagged with
30 views

1 vote
51 views

### How to obtain a recurrence relation for Taylor series coefficients?

Recently, I asked WolframAlpha to give me the first few terms in the Taylor series for a complicated (but well-behaved) function. It did so, but also provided a recurrence relation for the ...
• 13
56 views

### Solving the recurrence relations with boundary conditions

This is the recurrence relation: $$a_r - 4a_{r-1} + a_{r-2} = 1 + 2^r$$ and we have to solve this with boundary conditions $a_0 = 1$ and $a_1 = 2$. I found the complementary solution, made the ...
• 224
35 views

### How do we prove this nested radical solution?

I’m submitting this question because my previous one was perhaps too verbose and did not get the point very quickly. A well known $\sqrt{2}$ nested radical has the following solutions as found in the ...
• 6,791
21 views

• 6,791
130 views

### Quadratic Recurrence Relations

Does anyone know combinatoric methods to get solutions to quadratic recurrences? An example of what I'm looking for: $$F_{n+1} = 3F_n^2-2F_n$$ under the initial condition $F_0 =2, F_1 = 8$. Much more ...
• 4,182
1 vote
59 views

### Cancelling terms in an infinite series over $\mathbb{N}^2$

I try to understand Don Zagiers seemingly simple proof of the recurrence relation \begin{align*} \sum_{0<j<k,\ j\ \text{even}}\zeta(j)\zeta(k-j)=\frac{k+1}{2}\zeta(k)\ \ \ \ \ \ \ \ \ \ \ \ \ \...
• 11
67 views

### A sequence is defined $P_n(x)=P_{n-1}(x-1)P_{n-1}(x+1)$for $n\ge1$ and $P_0(x)=x$. Find the largest $k$ such that $P_{2014}(x)$ is divisible by $x^k$.

I started by finding some of the polynomials and got $$P_1(x)=x^2-1$$$$P_2(x)=x^2(x^2-4)$$$$P_3(x)=(x^2-1)^3(x^2-9)$$$$P_4(x)=x^6(x^2-4)^4(x^2-16)$$$$P_5(x)=(x^2-1)^{10}(x^2-9)^5(x^2-25)$$ but I’m ...
• 499
1 vote
64 views

### What field should I search to solve delay like equations?

I want to solve equations like: $$t f(t) + u(t-2) f(t-2) = \sin(t)$$ It's like delay differential equations but without the derivative. What field should I search in to solve this kind of equation?
• 1,118
80 views

### $\Theta$-notation of the recurrences $T(n) = 3T(n/2 +1) + n$ and $T(n) = 4T(n/2)-4T(n/4)+1$ [closed]

(a) $T(n) = 3T \left ( \frac{n}{2} + 1 \right ) + n$ (b) $T(n) = 4T \left ( \frac{n}{2} \right ) - 4 T \left ( \frac{n}{4} \right ) + 1$ I am really stuck on these two recurrences and finding out ...
• 33
39 views

### Properties of substitution system

I'm interested in automatic sequence or substitution systems. I focused on the simplest form with a binary alphabet without constants. A well-known example is Thue-Morse sequence with axiom ...
• 770
1 vote
56 views

### Number of sequences of length $n \geq 1$ with elements from set $\{0,1,2,3,4 \}$ such that blocks of $0$s, $2$s and $4$s are of even length.

Question statement: In a sequence $\langle a_1, ...,a_n \rangle$ a block is every maximal subsequence of same digits. For example, in a sequence $\langle 0, 0, 3, 1, 2, 2, 2, 2, 4, 4 \rangle$ there ...
• 1,047
1 vote
40 views

### Recurrence and Asymptotic

Given this recurrent relation $$a_{n+1} \leq a_n-ka_n^2,\ k>0$$ How can I prove this asymptotic behavior not using induction? $$a_n\leq\frac{1}{nk+a_0^{-1}}$$ I ran this numerically on MATLAB and ...
### Diophantine just with a recurring solution $XY=a^2(ab+1)=K$ (without calculating all K divisors)
I am trying to get a recurring solutions for this kind of Diophantine equation: $XY=a^2(ab+1)=K$; where $a,b \in$ $\Bbb N$ and $a=even$ First of all, I am industrial engineer, sorry for that :) and if ...
### Prove that $\lim_{n\rightarrow\infty}\frac{f(n)}{n!}=e$
Prove that $$\lim_{n\rightarrow\infty}\frac{f(n+1)}{n!}=e\tag{1}$$where $$f(n+1)=n(1+f(n))$$ The recurrence relation of $n!$ is $a_n=na_{n-1}$ or $a_{n+1}=(n+1)a_n$. I thought of making a new ...