Suppose we have relation
$T(n,k)=\begin{cases}
T(n,k)=T(n-1,k-1)+T(n-1,k)+1, & \\
1,\text{$k=0 \text{ or } n=k$}
\end{cases}
$.
Now we relate above relation to $C(n,k)$.
Let $C(n,k)=T(n,k)+1$ then
$C(n,k)=C(n-1,k-1)+C(n-1,k)$ this is exactly relation binomial coefficients.
Now i want prove that $C(k,n)=2\binom{n}{k}$
, But when i use iduction on $k,n$ get stuck. How i can use induction on this problem?
My attempt:(i read this post)
First i define $P(t)$ such that $t=k+n$, and $0\leq k\leq n$ , and $C(n,k)=2\binom{n}{k}$, now main problem is how i can relate $P(t+1)$ to $P(t)$? Any hint be appreciated.
Best Answer
As your question states,
$$C(n,k) = T(n,k) + 1, \; C(n,k) = C(n-1,k-1) + C(n-1,k) \tag{1}\label{eq1A}$$
You've also defined $P(t)$ for $t \ge 0$ as
$$k + n = t, \; 0 \le k \le n, \; \implies \; C(n,k) = 2\binom{n}{k} \tag{2}\label{eq2A}$$
Due to the use of $(n - 1) + (k - 1) = (n + k) - 2 = t - 2$ and $(n - 1) + k = (n + k) - 1 = t - 1$ on the right side of \eqref{eq1A}, this requires using strong induction, with $2$ base cases.
First, $P(0)$ requires $k = n = 0$. This gives $C(0,0) = T(0,0) + 1 = 1 + 1 = 2 = 2\binom{0}{0}$. Next, $P(1)$ has $k = 0$ and $n = 1$, with $C(1, 0) = T(1, 0) + 1 = 1 + 1 = 2 = 2\binom{1}{0}$. Thus, both of the base cases, i.e., $P(0)$ and $P(1)$, are satisfied.
Next, the inductive step is to assume $P(t)$ is satisfied for all $t \le m$ for some integer $m \ge 1$. For $P(m + 1)$, which has
$$k + n = m + 1, \; 0 \le k \le n \tag{3}\label{eq3A}$$
there are $3$ cases to consider. First, if $k = 0$, then $n = m + 1$, with $C(m + 1, 0) = T(m + 1, 0) + 1 = 1 + 1 = 2 = 2\binom{m + 1}{0}$, so $P(m + 1)$ applies here. The second case is with $k = n$, giving $C(n, n) = T(n, n) + 1 = 1 + 1 = 2 = 2\binom{n}{n}$, so $P(m + 1)$ is also satisfied. The third case is with $1 \le k \le n - 1$. Using \eqref{eq3A}, we have
$$(n - 1) + (k - 1) = n + k - 2 = m - 1, \; 0 \le k - 1 \lt n - 1 \tag{4}\label{eq4A}$$
$$(n - 1) + k = n + k - 1 = m, \; 0 \lt k \le n - 1 \tag{5}\label{eq5A}$$
Thus, by the inductive step, $P(m - 1)$ and $P(m)$ applies to the terms on the right side in \eqref{eq1A}. This therefore gives, while also using Pascal's rule, that
$$\begin{equation}\begin{aligned} C(n,k) & = C(n-1,k-1) + C(n-1,k) \\ & = 2\binom{n-1}{k-1} + 2\binom{n-1}{k} \\ & = 2\left(\binom{n-1}{k-1} + \binom{n-1}{k}\right) \\ & = 2\binom{n}{k} \end{aligned}\end{equation}\tag{6}\label{eq6A}$$
which shows $P(m+1)$ applies in this third case as well. This therefore proves using strong induction that $P(t)$ in \eqref{eq2A} is true for all $t \ge 0$.