# Questions tagged [recurrence-relations]

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

8,240 questions
Filter by
Sorted by
Tagged with
1 vote
27 views

50 views

• 739
1 vote
19 views

### Combinatorics, 2-Tree, Sequence

I've just thought about a combinatoric problem. Say you have a tree with $n$ nodes at the $n$-th level ($2$-tree). Number elements based on their position left to right, top to bottom. Let $a_{n,i}$ ...
51 views

### Fibonacci sequences within the Fibonacci sequence recurrence

I'm trying to perform a runtime analysis of the following simple recursive Fibonacci number algorithm: ...
• 75
134 views

### Possible positions of the knight after moving $n$ steps in Chessboard.

Problem There is a knight on an infinite chessboard. After moving one step, there are $8$ possible positions, and after moving two steps, there are $33$ possible positions. The possible position after ...
• 823
18 views

### Reference Request: Implicit Difference Equations

I know that there are some studies on implicit differential equations such as $$f(x, y, y') = 0.$$ I did some search but found very few results on the discrete version---implicit difference ...
85 views

### Find the number of ways of tiling a rectangular grid with dominoes

I'm trying to find the number of ways $(a_n)$ of tiling a rectangular grid with dominoes. I want to find a recurrence relation for $(a_n)$.
1 vote
60 views

### If $𝑓∘𝑔∘ℎ=𝑓 ∧ 𝑔∘ℎ∘𝑓=𝑔$ then must $ℎ∘𝑓∘𝑔=ℎ$?

If not, then What can be said of each $𝑓,𝑔,ℎ$ and are there any simpy-definable minimal conditions imposable upon one or more of the indexable functions that would ensure this symmetric closure? ...
34 views

74 views

### Find a simple path in given tree with minimum number of edges

Suppose given a Tree $T=(V,E)$. Each nodes in $T$ has a degree at most two. Also, edges in $T$ has weight distinct and positive natural. Suppose $|V|=n$, our goal is find a simple path with length ...
• 1
27 views

• 15.4k
16 views

• 235
1 vote
56 views

### Quadratic first order recurrence relation, is there a solution?

I am trying to find a solution for $a_n$, writing $a_n$ as a function of $n$, according to the following recurrence relation: $$a_n=3.9*a_{n-1}(1-a_{n-1}) ; a_0 = \frac{1}{2}$$. I have tried ...
• 13