Recurrence relation in $2$ variables

Question

Given a recurrence relation $func(n,k) = func(n-1,k) + func(n-1,k-1)$ with base cases $func(n,1) = n$ and $func(1,k) = 1$. How can I obtain its solution?

Answer 1

Assumption

$$p_{n,k}=\begin{cases} P(n,k)&\text{if }n\ge k\ge0 \\0&\text{otherwise} \end{cases}$$

$p_{n,0}=1$

$$\begin{align}&p_{n+1,1}=p_{n,1}+p_{n,0}\\ \implies &n+1=n+p_{n,0}\\\implies &p_{n,0}=1\end{align}$$

You can use generating functions. Let $$\begin{align} &g(x,y)=\sum_{n\ge0}\sum_{k\ge0}p_{n,k}x^ny^k=\sum_{n\ge1}\sum_{k\ge1}p_{n,k}x^ny^k+\sum_{n\ge0}p_{n,0}x^n\\ &=\sum_{n\ge 1}\sum_{k\ge1}p_{n-1,k}x^ny^k+\sum_{n\ge 1}\sum_{k\ge1}p_{n-1,k-1}x^ny^k+{1\over1-x}\\ &=x\sum_{n\ge0}\sum_{k\ge1}p_{n,k}x^ny^k+xy\sum_{n\ge 0}\sum_{k\ge0}p_{n,k}x^ny^k+{1\over1-x}\\ &=x\left(g(x,y)-\sum_{n\ge0}p_{n,0}x^n\right)+xyg(x,y)+{1\over1-x}\\ &=x(1+y)g(x,y)+{1\over1-x}(1-x)=x(1+y)g(x,y)+1\\ \therefore& \;g(x,y)={1\over 1-x(1+y)}=\sum_{n\ge0}x^n(1+y)^n\\ =&\sum_{n\ge0}\sum_{k=0}^n\binom{n}{k}x^ny^k\\ \therefore& \;P(n,k)=\binom{n}{k} \quad\forall n\ge k\ge0 \end{align}$$ As expected from the recursion.