Growth of binomial recurrence with different initial conditions

55 Views Asked by At

The binomial coefficients $\binom{n}{r}$ satisfies $\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$. This means it is a solution of the equation $f(n,r)=f(n-1,r)+f(n-1,r-1)$, with initial conditions $f(n,0)=1$ for $n\geq 0$, and $f(0,r)=0$ for $r>0$.

For any other initial conditions, for example $f(n,0)=a$ for $n\geq 0$, and $f(0,r)=b$ for $r>0$ (for some fixed $a,b\geq 0$), is the growth rate of $f$ similar to that of the binomial coefficients? For example, is it true that $$f(n,r)\leq K_{a,b}\binom{n}{r}$$ for some constant $K_{a,b}$ depending on $a,b$?

1

There are 1 best solutions below

0
On BEST ANSWER

It's clear that : $$f(n,r)\leq \max(a,b)\binom{n}{r}$$ And you can even write an expression of $f(n,r)$ : $$f(n,r)=\dbinom{n-1}{r}a+\dbinom{n-1}{r-1}b$$ You can prove it by induction, note also that the equality holds when $a=b$ First terms of the sequence:

$1\\ a\ \ \ \ b\\ a\ \ \ \ a+b\ \ \ \ b\\ a\ \ \ \ 2a+b\ \ \ \ a+2b\ \ \ \ b\\$