Intereting Posts

Asymptotic expressions of $\pi_{2}(n), \pi_{4}(n)$ and $\pi_{6}(n)$
If $dF_p$ is nonsingular, then $F(p)\in$ Int$N$
Determinant of a tensor product of two vector bundles
Why do we study prime ideals?
Why does $\lim_{n\to\infty}(1+\frac{1}{n})^n = e$ instead of $1$?
Calculate the following infinite sum in a closed form $\sum_{n=1}^\infty(n\ \text{arccot}\ n-1)$?
$p$-group and normalizer
If $n\equiv 4 \pmod 9$ then $n$ cannot be written as sum of three cubes?
Proving an inequality about a sequnce with Cauchy-Schwarz
Orientable Surface Covers Non-Orientable Surface
How to make 3D object smooth?
Cubic diophantine equation
Why are x and y such common variables in today's equations? How did their use originate?
Integral Basis for Cubic Fields
Frattini subgroup of a finite group

How to approach the following two dimensional recurrence relation ?

For $i,j\ge2$,

$$a_{i,\ j}\ =\ a_{i,\ j-1}\ +\ a_{i-1,\ j-1}$$

where $a_{p,\ 1}=1$ (for $p\ge1$) and $a_{1,\ q} = 1$ (for $q\ge1)$.

- Question about generating function in an article
- In how many different ways can we fully parenthesize the matrix product?
- Period of a sequence defined by its preceding term
- We define a sequence of rational numbers {$a_n$} by putting $a_1=3$ and $a_{n+1}=4-\frac{2}{a_n}$ for all natural numbers. Put $\alpha = 2 + \sqrt{2}$
- Recurrence equation question
- Limit of the sequence $a_{n+1}=\frac{1}{2} (a_n+\sqrt{\frac{a_n^2+b_n^2}{2}})$ - can't recognize the pattern

- Proof Using the Monotone Convergence Theorem for the sequence $a_{n+1} = \sqrt{4 + a_n}$
- Recurrence relation by substitution
- Closed form for the sequence defined by $a_0=1$ and $a_{n+1} = a_n + a_n^{-1}$
- Fibonacci, tribonacci and other similar sequences
- How to deduce a closed formula given an equivalent recursive one?
- Making an infinite generating function a finite one
- How is Ramanujan's recurrence relation for his nested radical solved?
- How to solve $ \sqrt{x^2 +\sqrt{4x^2 +\sqrt{16x^2+ \sqrt{64x^2+\dotsb} } } } =5\,$?
- Prove conjecture $a_{n+1}>a_{n}$ if $a_{n+1}=a+\frac{n}{a_{n}}$
- Why is solving non-linear recurrence relations “hopeless”?

One way to go about this and generally about solving recurrence relations is to use generating functions, in this case this will lead to two variable generating function.

Let’s suppose we have $f(x,y)=\sum_{i,j=0}^{\infty}a_{i,j} x^i y^j$ formal powers series which encodes coefficients of your sequence. For simplicity, here we have it shifted, so actually $a_{0,q}=a_{p,0}=1$, but don’t worry about that, we can shift this back at the end. Now let’s play with coefficients a little to see if we can get better form of $f(x,y)$:

\begin{align}

f(x,y)&=\sum_{i,j=0}^{\infty}a_{i,j} x^i y^j \\

&=a_{0,0}+\sum_{i=1}^{\infty}a_{i,0} x^i+\sum_{j=1}^{\infty}a_{0,j} y^j + \sum_{i,j=1}^{\infty}a_{i,j} x^i y^j \\

\end{align}

Now we have shifted the indices (you will see later why), but before proceeding, notice $a_{0,0}=1$ and that

$$

\sum_{i=1}^{\infty}a_{i,0} x^i = x+x^2+x^3+\dots = \frac{x}{1-x}

$$

and similarly for the second sum. So overall we have

$$

f(x,y) = 1+\frac{x}{1-x}+\frac{y}{1-y}+\sum_{i,j=1}^{\infty}a_{i,j} x^i y^j

$$

Now for the rightmost sum, lets write

\begin{align}

\sum_{i,j=1}^{\infty}a_{i,j} x^i y^j &= \sum_{i,j=1}^{\infty}(a_{i,j-1}+a_{i-1,j-1}) x^i y^j \\

&= \sum_{i,j=1}^{\infty}a_{i,j-1} x^i y^j+\sum_{i,j=1}^{\infty}a_{i-1,j-1} x^i y^j \\

&= y\sum_{i,j=1}^{\infty}a_{i,j-1} x^i y^{j-1}+xy\sum_{i,j=1}^{\infty}a_{i-1,j-1} x^{i-1} y^{j-1}\\

\end{align}

Here we have just applied the recurrence relation (this is why we moved the $0$ indices out before) and then moved the $x$,$y$ out of the sum, so that indices match. Now lets just re-index the sum

\begin{align}

\sum_{i,j=1}^{\infty}a_{i,j} x^i y^j &= y\sum_{i,j=1}^{\infty}a_{i,j-1} x^i y^{j-1}+xy\sum_{i,j=1}^{\infty}a_{i-1,j-1} x^{i-1} y^{j-1}\\

&= y\sum_{i=1,j=0}^{\infty}a_{i,j} x^i y^{j}+xy\sum_{i,j=0}^{\infty}a_{i,j} x^{i} y^{j}\\

&= y\left(\sum_{i=0,j=0}^{\infty}a_{i,j} x^i y^{j}-\sum_{j=0}^{\infty}a_{0,j}\right)+xy\sum_{i,j=0}^{\infty}a_{i,j} x^{i} y^{j}\\

&= y\left(f(x,y)-\sum_{j=0}^{\infty}a_{0,j}\right)+xyf(x,y)\\

&= y\left(f(x,y)-\frac{1}{1-y}\right)+xyf(x,y)\\

\end{align}

Here we have just substituted back the definition of $f(x,y)$ itself. Now putting back together we have

\begin{align}

f(x,y)=1+\frac{x}{1-x}+\frac{y}{1-y}+ y\left(f(x,y)-\frac{1}{1-y}\right)+xyf(x,y)\\

\end{align}

and after some simple algebraic manipulations we finally get:

\begin{align}

f(x,y) = \frac{1}{(1-x)(1-y-xy)}\\

\end{align}

Now the $f(x,y)$ encodes all of the coefficients in a compact way. We can now try to write it in a way that will allow us to see the coefficients more clearly.

For this notice that $\frac{1}{1-x}=1+x+x^2+x^3+\dots$. Also second expression is well known generating function $$\frac{1}{1-y-yx}=\frac{1}{1-y(x+1)}=\sum_{i,j=0}^{\infty}\binom{j}{i} x^i y^j.$$

So we can view our function in this form as a product

$$

f(x,y) = (1+x+x^2+x^3+\dots) \left(\sum_{i,j=0}^{\infty}\binom{j}{i} x^i y^j\right)

$$

Now to ask what is the value of $a_{i,j}$ is same as to ask what coefficient of $x^i y^j$ is in this product. It is not hard to see that it will be $\binom{j}{i}+\binom{j}{i-1}+\dots+\binom{j}{0}$. So overall, also with correcting the original offset from $i$ to $i-1$ and $j$ to $j-1$, we get

$$a_{i,j} = \sum_{k=0}^{i-1}\binom{j-1}{k}.$$

- Why are $3D$ transformation matrices $4 \times 4$ instead of $3 \times 3$?
- minimum and maximum problem
- How can I show this set of sequences is compact?
- A combinatorial proof that the alternating sum of binomial coefficients is zero
- Geometric interpretation and computation of the Normal bundle
- Equivalence relation on $\mathbb{N}$ with infinitely many equivalence classes
- Radius of convergence of Taylor series of holomorphic function
- Polynomials over finite fields
- $A \in B$ vs. $A \subset B$ for proofs
- Understand a proof concerning a theorem about topologically equivalent systems
- Graph with girth 5 and exactly $k^2+1$ vertices
- Does same cardinality imply a bijection?
- Prove $\lim_{x\rightarrow 0}\cos (x)=1$ with the epsilon-delta definition of limits
- Ring homomorphisms $\mathbb{R} \to \mathbb{R}$.
- A group generated by two elements such that its product with itself is not generated by two elements.