According to asked question in this post.

Suppose $T(n,k)=T(n-1,k-1)+T(n-1,k)+1$, now let $C(n,k)=T(n,k)+1$.

As a result $C(n,k)=C(n-1,k-1)+C(n-1,k)$.

I want to prove $C(n,k)=2\binom{n}{k}$, now on that post mentioned that use induction to prove equality such that induction on $k+n$. My problem is when i use induction on $k+n=m$, And define $P(m)$ I can't accurately prove. For example: when i try to prove $P(2)$, i set $k=0,n=2$ or $k=1,n=1$ and for $P(2)$ we have two cases. Anyone can help me to prove it ?

$P(m)$ states that whenever $0≤k≤n$ and $k+n=m$ then $C(n,k)=2\binom{n}{k}$

  • 1
    $\begingroup$ You can read this link , and get the right answer $\endgroup$
    – user133300
    Mar 19 at 13:26

This site is temporarily in read only mode and not accepting new answers.