Question

How do you use strong induction to show that the coefficient of x^2 in the expansion of (1+x+x^2+...x^n)^n is (1+2+...n)?

Answer 1

We will use strong induction on n to show that the coefficient of   in the expansion of    is .

Base Step : For n = 2 ,

  

So the coefficient of is 1+2 .

So the statement is true for n=2 .

Induction Hypothesis : Suppose the statement is true for all n such that that is if then coefficient of      is .

Induction Step :

  

Now , have coefficient   , 1+2+3+...+n

   have coefficient of , n+1 .

Hence in the expansion coefficient of is 1+2+3+...+n+(n+1) .

So the statement is true for n=2 and the statement is true for n+1 if it is true for n . Hence by induction the statement is true for all natural number n greater than 2 .

N.B- The statement is not true for n=1 .

.

If you have any doubt please comment .