Combinatorics proof of summation of 3^n

[mahjk17]

Hi, I am new here and I am stuck on a problem. I am in a combinatorics class and the question is based on proving by both a counting argument (binomial coefficient) and by induction of the equation below. Can you provide me in great detail on how to start a binomial proof to prove this? It's my first discrete math class and I am having trouble grasping the concepts. Thank you very much !!!!

∑[i=0,k](k,i)*2^i = 3^k

 

[daon2]

Show it is true for n=0. Easy?

Assume your proposition is true for all values less than a fixed \(\displaystyle n\). That is, assume for all \(\displaystyle k\le n\) the following is true:

\(\displaystyle \sum_{i=0}^k {k\choose i} 2^i = 3^k\)

Use this assumption to show it is true for \(\displaystyle n+1\), that is, show:

\(\displaystyle \sum_{i=0}^{n+1} {n+1\choose i} 2^i = 3^{n+1}\).

Note that a more general statement is true: http://www.wolframalpha.com/input/?i=sum+(i=0+to+n)+C(n,i)*k^i

Yours is just the binomial expansion of \(\displaystyle (2+1)^n\)

 

[mahjk17]

Show it is true for n=0. Easy?

Assume your proposition is true for all values less than a fixed \(\displaystyle n\). That is, assume for all \(\displaystyle k\le n\) the following is true:

\(\displaystyle \sum_{i=0}^k {k\choose i} 2^i = 3^k\)

Use this assumption to show it is true for \(\displaystyle n+1\), that is, show:

\(\displaystyle \sum_{i=0}^{n+1} {n+1\choose i} 2^i = 3^{n+1}\).

Note that a more general statement is true: http://www.wolframalpha.com/input/?i=sum+(i=0+to+n)+C(n,i)*k^i

Yours is just the binomial expansion of \(\displaystyle (2+1)^n\)

Thank you very much for the reply!
I understand the induction part , where I have to use pascal identity and manipulate it to proof it but is there another easier way to prove this instead of induction ??? And also I dont understand your last comment where you said, "yours is just the binomial expansion of (2+1)^n" Thank you !!!

 

[tkhunny]

Of course, you mean "Strong Induction".

If you wish to prove for ALL positive integers, this is likely the way to go. If you are particularly astute, you can apply the Well-Ordering Principle and give it a go.

 

[daon2]

Thank you very much for the reply!
I understand the induction part , where I have to use pascal identity and manipulate it to proof it but is there another easier way to prove this instead of induction ??? And also I dont understand your last comment where you said, "yours is just the binomial expansion of (2+1)^n" Thank you !!!

The famous Binomial Theorem is:

\(\displaystyle \displaystyle \sum_{i=0}^n {n \choose i}a^ib^{n-i} = (a+b)^n\).

That is how one would calculate \(\displaystyle (x+1)^3 = x^3 + 3x^2 + 3x + 1\) without having to "FOIL" everything out. All one has to do is remember the coefficients 1,3,3,1.

See: http://en.wikipedia.org/wiki/Binomial_theorem

You are proving a lil' baby version where \(\displaystyle a=2\) and \(\displaystyle b=1\).

Induction for this kind of question is pretty standard. There is a proof of the binomial theorem on the wikipedia page. Perhaps use that as a guide for you question.

 

[mahjk17]

Thank you all very much, especially daon2 !!!!