I want to understand the following recurrence relation from https://oeis.org/A140993. I see the triangle it creates, but I don't understand how to generate the triangle from the formula.
Can someone explain it and give an example of calculating a few levels of it?
Triangle read by rows:
recurrence G(n,k): G(n, n)=G(n+1, 1)=1,
G(n+2, 2)=2,
G(n+3, k)=G(n+1, k-1)+G(n+1, k-2)+G(n+2, k-1) for k:=2..(n+2), 0<=k<=n.
Triangle begins:
1
1 1
1 2 1
1 2 4 1
1 2 5 7 1
1 2 5 11 12 1
1 2 5 12 23 20 1
1 2 5 12 28 46 33 1
1 2 5 12 29 63 89 54 1
1 2 5 12 29 69 137 168 88 1
1 2 5 12 29 70 161 289 311 143 1
1 2 5 12 29 70 168 367 594 567 232 1
1 2 5 12 29 70 169 399 817 1194 1021 376 1
1 2 5 12 29 70 169 407 934 1778 2355 1820 609 1
The number $G(n,k)$ appears in row $n$, column $k$ of the array. We’re told that $G(n,n)=1$ for all $n\ge 1$, so the diagonal is all ones. This includes $G(1,1)$, the element at the top of the array. We’re also told that $G(n+1,1)=1$ for all $n\ge 1$; that says that $G(n,1)=1$ for $n\ge 2$, and we already knew that $G(1,1)=1$, so the entire first column is all ones. So far we have this:
$$\begin{array}{c|cc} n\backslash k&1&2&3&4&5\\ \hline 1&1\\ 2&1&1\\ 3&1&-&1\\ 4&1&-&-&1\\ 5&1&-&-&-&1 \end{array}$$
Next we learn that $G(n+2,2)=2$ for all $n\ge 1$; that is, $G(n,2)=2$ for all $n\ge 3$. Now we have:
$$\begin{array}{c|cc} n\backslash k&1&2&3&4&5\\ \hline 1&1\\ 2&1&1\\ 3&1&2&1\\ 4&1&2&-&1\\ 5&1&2&-&-&1 \end{array}\tag{1}$$
Finally we come to the main recurrence:
$$G(n+3,k)=G(n+1,k-1)+G(n+1,k-2)+G(n+2,k-1)\tag{2}$$
for $k=2,3,\ldots,n+1$. The use of $n+3$ really just says that we’re talking about row $4$ and later; we could instead write $(2)$ as
$$G(n,k)=G(n-2,k-1)+G(n-2,k-2)+G(n-1,k-1)\tag{3}$$
for $n\ge 4$ and $2\le k\le n-1$. This says that each entry whose value has not been determined by the earlier clauses of the definition of $G$ is the sum of three entries above and to the left of it, as you can see from the following small piece of the array:
$$\begin{array}{|c|c|c|} \hline G(n-2,k-2)&G(n-2,k-1)\\ \hline &G(n-1,k-1)\\ \hline &&G(n,k)\\ \hline \end{array}$$
The first missing entry in $(1)$ is $G(4,3)$; according to $(3)$, this is
$$G(4,3)=G(2,2)+G(2,1)+G(3,2)=1+1+2=4\;,$$
as also shown by the brown and red entries below:
$$\begin{array}{c|cc} n\backslash k&1&2&3&4&5\\ \hline 1&1\\ 2&\color{brown}1&\color{brown}1\\ 3&1&\color{brown}2&1\\ 4&1&2&\color{red}4&1\\ 5&1&2&-&-&1 \end{array}$$
Similarly,
$$G(5,3)=G(3,2)+G(3,1)+G(4,2)=2+1+2=5\;:$$
$$\begin{array}{c|cc} n\backslash k&1&2&3&4&5\\ \hline 1&1\\ 2&1&1\\ 3&\color{brown}1&\color{brown}2&1\\ 4&1&\color{brown}2&4&1\\ 5&1&2&\color{red}5&-&1 \end{array}$$
Finally,
$$G(5,4)=G(3,3)+G(3,2)+G(4,3)=1+2+4=7\;:$$
$$\begin{array}{c|cc} n\backslash k&1&2&3&4&5\\ \hline 1&1\\ 2&1&1\\ 3&1&\color{brown}2&\color{brown}1\\ 4&1&2&\color{brown}4&1\\ 5&1&2&5&\color{red}7&1 \end{array}$$
And the array continues to grow in this fashion.