# Questions tagged [recurrence-relations]

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

8,585 questions
Filter by
Sorted by
Tagged with
1 vote
17 views

### Probability to reach $n+1>0$ before returning to the origin in an asymmetric one dimensional random walk.

Let's say we take one dimensional random walk. The origin is at point $0$ and next, there are $n+1$ integres, so we have: $0, 1, 2, 3, 4, ... n+1$. W start in the point $1$ from which we make a $1$ ...
• 363
1 vote
22 views

### Obtaining a single value of EGF in terms of multiple OGF evaluations?

I have access to ordinary generating function $f$ which I can evaluate at $d$ arbitrary real-valued points $f(s_1),f(s_2),\ldots,f(s_d)$. I need to know the approximate value of $g(t_1)$, which is the ...
• 4,990
1 vote
31 views

### Solve two-variable recursion using generating function

Suppose $T(n,k)$ satisfies the nitial condition $T(0,k)=\delta_{k,1}$ and the recursion $$T(n,0)=qT(n-1,1),\quad T(n,1)=qT(n-1,2),$$ $$T(n,k)=qT(n-1,k+1)+pT(n-1,k-1), k>1.$$ Playing around, I ...
• 1,677
57 views

### Does a bijective function exists behind every recurrence relation?

Consider these 2 questions where recurrence relations can be applied: Q1) Given an (nxm) where n denotes rows and m denotes columns of a grid, find the number of unique paths ($a_{n,m}$) that goes ...
29 views

### Why does this application of Jacobsthal numbers defined by the recurrence relation: $a_n$ = $a_{n-1}$ + 2$a_{n-2}$ work in 2D tiles / grids?

Problem Statement: Find the Recurrence Relation for $a_n$, where $a_n$ is the number of ways to tile a (2xn) rectangular board with (1x2) or (2x2) pieces. . . Note: A (1x2) piece can be placed either ...
45 views

• 89
16 views

### Recurrence Relation for Longest Increasing Subsequence Problem

I am trying to solve the Longest Increasing Subsequence(LIS) Problem using different OPT Function than the one which normally used. I have been given this question as an extra credit and I have been ...
• 1
54 views

1 vote
42 views

### Using inequality $\sum_{k-2}^{n-1} k \log k \leq \frac{1}{2} n^2 \log n - \frac{1}{8} n^2$ to show the recurrence of quicksort runtime

Use the inequality $$\sum_{k=2}^{n-1} k \log k \leq \frac{1}{2} n^2 \log n - \frac{1}{8} n^2$$ To show that $$C_n = \frac{2}{n}\sum_{i=2}^{n-1}C_i + \Theta(n)$$ is $\Theta(n \log n)$ This is an ...
• 1,329
58 views

### Solve a 2D linear recurrence

I need to know the solution of this recurrence: $$2a[n,k-1]-a[n-1,k-1]-2a[n-1,k-2]+a[n-2,k-2]=a[n,k]$$ With the initial value unspecified. Also, wolfram is good at solving linear 1D recurrence, but ...
54 views

• 21
62 views

### On the limit defined by $A + B(A + B(A + B (A + B(\cdots))))$

Suppose $A$ and $B$ are some constant ($A,B\in\mathbb{R}$) Is there a simple expression for $x$, where $x$ is: $$x=A+B[A+B[A+B[\cdots]]]]$$ "..." indicates the pattern repeats forever. In ...
• 152
27 views

### Concrete Mathematics - The Josephus Problem for $J(2^m)=1$

I've been going through Concrete Mathematics and have a question on the Josephus problem. Recurrence relation: $$\begin{split} J(1)&=1\\ J(2n)&=2J(n)−1\\ J(2n+1)&=2J(n)+1 \end{split}$$ ...
36 views

### What will be the base case here in this recurrence relation?

Problem: Lorenzo takes up a loan of 40,000. It is to be paid by annual installments of 2000 with first payment made at the end of the first year the loan was taken out. 3% interest is charged at the ...
• 2,923
30 views

### Solving a recursive equation [duplicate]

So I'm working on a combinatorics problem, to which I've reached that $$f(1)=1, f(n)=1+\frac{1}{n}\sum_{k=1}^{n-1} f(k)$$ I have been working at this problem for a few days now, and I am fairly ...
• 47
1 vote
44 views

• 7,755
94 views

### Proof of alternating zeros of Bessel function

We will be dealing with the Bessel functions of the first kind. Notice that to prove that their zeroes are alternating, one can just prove that for every two zeroes for $J_\nu(x)$ there exists a zero ...
• 1,789
31 views

### A Bessel function inspired recurrent sum

I came up upon the following recurrent sum. $a\cdot (B_{n-1}\cdot e^{i\cdot k_0 \cdot z}+ B_{n+1}\cdot e^{-i\cdot k_0 \cdot z})=2 \cdot n \cdot B_n$ Where $a$ is complex , $k_0$ and $z$ are real, $n$ ...
### Prove the recurrence relation $T(n) = 2T(n/2) + n$ is equal to $n\log(n) + n$ using induction
Question Given the recurrence relation for the Merge Sort algorithm: $T(n) = 1$, if $n = 1$ $T(n) = 2T(n/2) + n$, if $n > 1$ Prove by induction that $T(n) = n\log(n) + n$ and hence $O(n\log(n))$ My ...
Suppose $S_k = \sum_{i=0}^k \binom{k}{i} \frac{\left(a\right)_i\left(b\right)_{k-i} x^i} {\left(c\right)_i\left(d\right)_{k-i}}$, where $(a)_i = a(a+1)\cdots (a+i-1)$. Note that the above sum can also ...