# Questions tagged [recurrence-relations]

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

8,245 questions
Filter by
Sorted by
Tagged with
18 views

### Difference between self-similarity and recurrence

For me intuitively self-similarity and recurrence are not exactly the same, however a lot of self-similar objects like fractals are defined via a recurrent equation. Is there a self-similar object ...
28 views

37 views

### Getting rid of asymptotic notation in Recurrence Relations

Let's suppose I want to resolve the following Recurrence Relation: $$T(n) = \begin{cases} 1 & n=1 \\ T(n-1) + \Theta(n) & \text{otherwise} \end{cases}$$ I want to prove that ...
• 101
87 views

### Using a generating function to solve a recursion

I know that the generating function for the sum of Fibonacci numbers with even index is \begin{align} F_e(z) &= \sum_{n \ge 0} F_{2 n} z^n \\ &= \frac{F(z^{1/2}) + F(- z^{1/2})}{2} \\ &...
• 189
37 views

60 views

### What is the value of $a_1a_2\cdots a_{2019}$?

Let $a_1=\frac 34$ and for any $n\geq2$ $4a_n=4a_{n-1}+\frac {2n+1}{1^3+2^3+\cdots n^3 }$. What is the value of $a_1a_2\cdots a_{2019}$? I tried $1^3+2^3+\cdots +n^3=\frac {n^2(n+1)^2}{4}$ and I ...
• 492
14 views

### Linear Recurrences approximation to exponential

I have been reading the solutions to the MIT primes 2011 solutions and am having trouble understanding their logic. The text basically says that if a_k = a_{k-1} + a_{k - 2} ... a_{k - n}, then a_k is ...
1 vote
284 views

### Recursive relation practice

My questions: Call a string of letters "legal" if it can be produced by concatenating (running together) copies of the following strings: 'v', 'ww', 'xx' 'yyy' and 'zzz'. For example, the ...
• 5
35 views

### If $s(n)=3n^2−3n+5$, then $s(n)=2s(n−1)−s(n−2)+c$ for all integers $n\ge 2$. What is the value of $c$?

Solve the following: If $s(n)=3n^2−3n+5$, then $s(n)=2s(n−1)−s(n−2)+c$ for all integers $n\ge2$. What is the value of $c$? How do I solve this question?
• 1
91 views

160 views

### Sum of a recursive series

Find $S_n=\sum_{k=1}^{x} a_{k}$ , where $a_1 = 1$ and $\forall k>1 : a_{k}=a_{k-1}+{\lfloor \sqrt {a_{k-1}} \rfloor}$ and $x$ is a natural number such that $a_{x} \leq n < a_{x+1}$. For simply ...
1 vote
44 views

### How do I solve this non-linear differential equation?

I have a formula describing a non-linear system which is as follows: $-y(x)'' + A|y(x)|^2y(x) = k^2 y(x)$ where A is a constant that I can choose to be a positive or negative integer. I also have ...
• 11
37 views

### Finding sequence [closed]

I'm looking for the pattern of this series -> $1, 2, 1, 2, 1, 2$. Any help would be appreciated. $S_k = 2/S_{k-1}, k \in \mathbb{Z}, k \ge 2, S_1 = 1.$
38 views

### particular solution form of $h_n - h_{n - 1} = 3 - n$

Particular solution form of $h_n - h_{n - 1} = 3 - n$ In the rhs, we have $-n$ is of the form : $h_n = -A_1n +A_2$ $3$ is of the form : $h_n = A_3$ because $A_2$ and $A_3$ are some numbers we can ...
• 21
66 views

• 133
91 views

### Given $x_{1} > 2$ and the recursively defined sequence $x_{n+1}=1+\sqrt{x_{n}-1}$

Given $x_{1} > 2$ and the recursively defined sequence $x_{n+1}=1+\sqrt{x_{n}-1}$. Proof: (a) $x_{n} \geq 2\ \forall n \geq2$ (which seems obvious given the initial condition, but I also would like ...
1 vote
74 views

### Is the following sequence $x_{n+1}$ = $x_{n} + 1/x_{n}$ convergent given $x_{1} >0$? [duplicate]

I got the following result : $x_{n+1} = x_{n}+\frac{1}{x_{n}}$ and so forth. As $x_{1}>0$, then I know by plugging that $x_{k}>1$ for every natural $k$. Hence, the terms in the denominator tend ...
81 views

85 views

• 335
61 views

• 381
56 views

### Question about a step in a derangement proof

I read a proof about derangement and I didn't understand this step: $d_n - nd_{n-1} = -(d_{n-1}-(n-1)d_{n-2}) \implies d_n=nd_{n-1}+(-1)^n$ I see that we have $S_n = -S_{n-1}$ if $S$ is the stuff on ...
• 119
### How do we solve the recurrence $T(n) = 2T(n/3) + n^{ \log_32 }\log\log n$?
How do we solve the recurrence $T(n) = 2T(n/3) + n^{ \log_32 }\log\log n$? Also, is it possible to solve this recurrence by the Master method?