$n,m$ are natural positive integers. F$(n,1)$=F$(1,n)=1$ F$(n,m+1)$+F$(n+1,m)=$F$(n+1,m+1)$ Write F($2,n$) and F($3,n$) as a function of $n$

Question

How do I solve this problem? I do not know where to begin nor does anyone close to me. I am lost and I need help. Thank you so much for whoever helps.

Answer 1

Picture a quarter-plane rectangular grid in $n$ and $m$. Then the equations $$ F(1,n) = F(n,1) = 1 $$ place the value $1$ along the edges of that grid. Now look at the equation $$ F(n+1,m+1) = F(n+1,m) + F(n, m+1) $$ Whenever we have an empty square with filled in values below and to the immediate left, we can now fill in that square using said equation. Fo for example $$F(2,2) = F(2,1) + F(1,2) = 1+1 = 2\\ F(3,2) = F(3,1) + F(2,2) = 1+2 = 3 \\ \vdots \\ F(n,2) = F(n,1) + F(n-1,2) = 1 + n-1 = n $$ And once you have filled in that row, $$F(2,3) = F(2,2) + F(1,3) = 2+1 = 3\\ F(3,3) = F(3,2) + F(2,3) = 3+3 = 6 \\ F(4,3) = F(4,2) + F(3,3) = 6+6 = 10 \\ \vdots \\ F(n,3) = F(n,2) + F(n-1,3) = n + \frac{n(n-1)}{2} = \frac{(n+1)n}{2} $$

Answer 2

Using the rules: $F(n,1)=F(n,1)=1; F(n+1,m+1)=F(n,m+1)+F(n+1,m)$: $$\begin{align}F(1,1)&=1;\\ F(1,2)&=F(2,1)=1;\\ F(2,2)&=F(1,2)+F(2,1)=2;\\ F(3,2)&=F(2,2)+F(3,1)=2+1=3;\\ F(2,3)&=F(1,3)+F(2,2)=1+2=3;\\ \vdots\end{align}$$ We get the Pascal triangle for $F(m,n)$: $$\begin{array}{c|c|c|c|c|c|c} m/n & 1 & 2 & 3 &4 &5&6&\cdots \\ \hline 1 & 1 & 1 & 1 &1&1&1 \\ \hline 2 & 1 & 2 & 3&4&5&6 \\ \hline 3 & 1 & 3 & 6&10&15&21\\ \hline 4 & 1 & 4 & 10&20&35&56\\ \hline 5 & 1 & 5 & 15&35&70&126\\ \hline 6 & 1 & 6 & 21&56&126&252\\ \hline \vdots \\ \end{array}$$ Hence: $$\begin{align}F(m,n)&= {m+n-2\choose n-1}=\frac{(m+n-2)!}{(n-1)!(m-1)!}.\\ F(2,n)&={n\choose n-1}=\frac{n!}{1!(n-1)!}=n.\\ F(3,n)&={n+1\choose n-1}=\frac{(n+1)!}{2!(n-1)!}=\frac{n(n+1)}{2}.\end{align}$$ Note: $F(m,n)=F(n,m)$.