A gambler tosses a coin, winning 1\$ on heads and losing 1\$ on tails. We know they got $t$ tails and $k+t$ heads, thus winning $k$\$. The total ways in which this could have happened is ${2t+k \choose t}$ and the number of ways such that they reached $k$\$ for the first time on the last toss they made (call this "the Catalan constraint") is given by the Catalan numbers: ${2t+k-1 \choose t}-{2t+k-1 \choose t-1}$. See here: Probability that random walk will reach state $k$ for the first time on step $n$.
Now, let $n(k,t)$ be the number of ways in which they get to $k$ for the first time on toss $2t+k$ (which we know from other means is the generalized Catalan numbers). Then, conditioning on the first toss, we get the recurrence:
$$n(k,t)=n(k-1,t)+n(k+1,t-1) \tag{1}$$
Both the total number of paths (total ways of getting to $k$\$ in $2t+k$ tosses), as well as the paths with the Catalan constraint (ways of getting to $k$\$ for the first time after $2t+k$ tosses) satisfy the recurrence above. The only difference is in the initial conditions. For both series, we have:
$$n(0,0)=1$$
For paths with the Catalan constraint;
$$n(0,t)=0 \;\;\forall \;\; t>0$$
While for un-constrained paths;
$$n(0,t)={2t \choose t}$$
There must be a way to go from the recurrence in equation (1) to the solutions for the counts of the two kinds of paths (depending on which starting conditions we substitute), using generating functions or other techniques. Is there a way to do this?
Note that @robjohn's answer in the question linked above does do this, but he uses the interpretation that these are paths on the grid. I was hoping for a solution that doesn't depend on this intuition and only equation (1) with the starting conditions.
Specifying the initial conditions explicitly. In addition to the recurrence given by equation (1) which both series satisfy, we have the following initial conditions:
Case-1:
Paths that satisfy the Catalan constraint.
$$n(0,0)=1$$
$$n(0,t)=0 \forall t>0$$
We know the solution of the recurrence in equation (1) with these initial conditions is:
$$n(k,t) = {2t+k-1 \choose t}-{2t+k-1 \choose t-1}$$
Case-2:
All paths (no constraint).
$$n(0,0)=1$$
$$n(0,t)={2t \choose t} \forall t>0$$
We know the solution of the recurrence in equation (1) with these initial conditions is:
$$n(k,t) = {2t+k \choose t}$$
Best Answer
We are trying to solve the functional equation $$f(n, k) = f(n-1, k) + f(n+1, k-1)$$ with different boundary conditions.
Case $1$
$$f(0, k) = \begin{cases} 1 & k = 0\\ 0 &\text{otherwise} \end{cases}$$
Case $2$
$$f(0, k) = \begin{cases} 1 & k = 0\\ \binom{2k}{k} &\text{otherwise} \end{cases}$$
Define the generating function $$F_n(x) = \sum_{k=0}^\infty f(n, k) x^k$$
Multiply the original equation by $x^k$ and sum over $k \geq 1$ to obtain
$$\sum_{k \geq 1} f(n, k) x^k = \sum_{k \geq 1} f(n-1, k) x^k + \sum_{k \geq 1} f(n+1, k-1) x^k$$
Or, $$F_n(x) - 1 = F_{n-1}(x) - 1 + x F_{n+1}(x)$$
Or, $$x F_{n+1}(x) - F_n(x) + F_{n-1}(x) = 0$$
The characteristic equation of the above recurrence relation for the generating function $F_n(x)$ is given by $$xm^2 - m + 1 = 0 \implies m = \frac{1 \mp \sqrt{1-4x}}{2x}$$
Hence the solution is $$F_n(x) = c_1 m_1^n + c_2 m_2^n$$ where $m_1 = \frac{1 - \sqrt{1-4x}}{2x} = \frac{2}{1+ \sqrt{1-4x}}$ and $m_2 = \frac{1 + \sqrt{1-4x}}{2x} = \frac{2}{1- \sqrt{1-4x}}$
Note that $m_2$ is not defined for $x = 0$
We assume that $F_n(x)$ is defined for $x = 0$ and hence we set $c_2 = 0$
Finally $$F_n(x) = c_1 \left(\frac{2}{1+ \sqrt{1-4x}}\right)^n$$
Since the coefficient of $x^k$ in $F_n(x)$ gives the value of $f(n, k)$, we need to calculate that value in order to find $f(n, k)$
Case $1$: In this case, $$F_n(0) = 1 \implies c_1 = 1 \implies F_n(x) = \left(\frac{2}{1+ \sqrt{1-4x}}\right)^n$$
The coefficient of $x^k$ in $F_n(x)$ or $$f(n, k) = \binom{n+2k-1}{k} - \binom{n+2k-1}{k-1}$$
Case $2$: In this case, $$F_n(0) = \sum_{k = 0}^\infty \binom{2k}{k} x^k = \frac{1}{\sqrt{1-4x}}$$
$$\implies c_1 = \frac{1}{\sqrt{1-4x}} \implies F_n(x) = \frac{1}{\sqrt{1-4x}} \left(\frac{2}{1+ \sqrt{1-4x}}\right)^n$$
The coefficient of $x^k$ in $F_n(x)$ or $$f(n, k) = \binom{n+2k}{k}$$