Let $T(n,m)$ be such that : $$T(n,m) \leq \sum\limits_{i=0}^{n}{{n}\choose{i}} T(i,m-1)$$ where $T(n,1) \leq 2^n$ and $n, m\in \mathbb{N}$.

I want to solve this recursive inequality in order to find a close form upper bound for $T(n,m)$.

The well known binomial theorem (more info on wikipedia here and here) teach us that : $$(a+b)^n = \sum\limits_{i=0}^{n}{{n}\choose{i}}a^{n-i}.b^i$$

I think that using this theorem we can prove that $$T(n,m) \leq 2^{nm}$$ but I'm not 100% sure if what I did was correct... And I would appreciate if someone could give a look at my proof below which is done by recurrence. Thanks :-)

Proof by recurrence :

At the lowest rank $m=1$ : $T(n,m) \leq 2^{nm}$ is trivially true, since $T(n,1) \leq 2^n$ is given.

For a rank $m > 1$ :

  • At rank $m-1$ : we suppose $T(n,m-1) \leq 2^{n(m-1)}$ true.
  • And at rank $m$, we have by definition : $$T(n,m) \leq \sum\limits_{i=0}^{n}{{n}\choose{i}} T(i,m-1)$$
  • Thus : $$T(n,m) \leq \sum\limits_{i=0}^{n}{{n}\choose{i}} 2^{i(m-1)}$$
  • That we can rewrite into : $$T(n,m) \leq \sum\limits_{i=0}^{n}{{n}\choose{i}} (2^{m-1})^i$$
  • Since by the binomial theorem we have : $$(a+b)^n = \sum\limits_{i=0}^{n}{{n}\choose{i}}a^{n-i}.b^i$$
  • And setting $b=2^{m-1}$ and $a=1$ we obtain : $$T(n,m) \leq (2^{m-1} + 1)^n$$
  • And since $(2^{m-1} + 1)^n \leq (2^{m-1} + 2^{m-1})^n$ we get : $$T(n,m) \leq 2^{mn}$$

End of proof

I still have a little doubt on the scope of validity of the proof, since there are two variables and I did the recurrence only on $m$. Is it also proven for every $n$ ? Is it correct to say that for any $n, m\in \mathbb{N}$ we have $T(n,m) \leq 2^{mn}$.

If what I did is correct, it seems that this method may be easily generalized and applied on a lot of different types of combinatorics problems leading to similar recurence formulas involving binomial coefficients... Could someone proofcheck my proof :-) and if similar technics already exist, maybe someone could give me the reference of a book or a tutorial explaining it ?

Thank you very much, Luz :-)

  • $\begingroup$ Just to clarify, are you looking to find the best bound possible, or will any bound be okay? The best bound possible would be obtained by replacing the $\leq$ signs with $=$ and trying to find an explicit expression for $T(n,m)$. $\endgroup$ – user49640 Apr 25 '17 at 2:32
  • $\begingroup$ well if you can propose a tight bound, you will make me happy :-) so ok for replacing $\leq$ by $=$. And what about the recursive proof ? Do you think it is correct and that $T(n,m) \leq 2^{mn}$ for all $m,n \in \mathbb{N}$ ? $\endgroup$ – Luz Apr 25 '17 at 13:10
  • $\begingroup$ Your proof looks correct to me. But I think the same method can be used to prove $T(n,m) \leq (m + 1)^n$, and that bound would be tight. $\endgroup$ – user49640 Apr 25 '17 at 17:32
  • $\begingroup$ Indeed you are right. Thank you :-) To prove that $T(n,m) \leq (m+1)^n$ : we see that at rank $m=1$ it is true since $T(n,m) \leq (1+1)^n$ and $T(n,m) \leq 2^n$ is given. At rank $m-1$ we suppose $T(n,m-1) \leq m^n$ true. And following the same method, we can use the binomial theorem on $T(n,m) \leq \sum\limits_{i=0}^{n}{{n}\choose{i}} m^i \times 1^{n-i}$ to obtain $T(n,m) \leq (m + 1)^n$. $\endgroup$ – Luz Apr 26 '17 at 8:36

As told in the previous comment : The proof looks correct. Furthermore, a better upper bound $(m+1)^n$ may be proposed for $T(n,m) = \sum\limits_{i=0}^{n}{{n}\choose{i}} T(i,m-1)$ where $T(n,1) = 2^n$ and $n, m\in \mathbb{N}$.

We can prove that $T(n,m) = (m+1)^n$ by proving at rank $m=1$ that it is true since $T(n,m) = (1+1)^n$ and $T(n,m) = 2^n$ is given. And at rank $m-1$ we suppose $T(n,m-1) = m^n$ true. And following the same method, we can use the binomial theorem on $T(n,m) = \sum\limits_{i=0}^{n}{{n}\choose{i}} m^i \times 1^{n-i}$ to obtain $T(n,m) = (m + 1)^n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.