MAT260 Assignment: Sums, Coefficients, and Combinatorial Proofs

This assignment solution covers several problems in combinatorics, including evaluating sums using the binomial theorem, finding coefficients in multinomial expansions, and proving combinatorial identities. Specifically, it evaluates a sum involving binomial coefficients and powers of -10, determines the coefficient of a term in the expansion of a multinomial expression, proves a combinatorial identity using set theory reasoning, and demonstrates an inductive proof. Furthermore, it finds the generating function for a given sequence and applies the multinomial theorem. The document concludes with a problem related to arranging letters with repetitions. Desklib provides this and other solved assignments to aid students in their studies.

Solution 1 :
To evaluatae the sum of
∑
k=0
n
¿ ¿
Using binomial theoerem we can have
( x + y )n=∑
k=0
n
(n
k ) xn−k yk
Now here x=1,y=-10
( 1−10 )n=∑
k=0
n
(n
k )1n−k (−10)k
(−9 )n=∑
k=0
n
(n
k )(−10)k
(−9 )n=∑
k=0
n
¿ ¿
Hecne we got final answer as
∑
k=0
n
¿ ¿
Solution 2 :
To find the coefficient of
u2 v3 z3 ∈ ( 3 uv−2 z+u+v )7
If we expand this then we get
2187*u^7*v^7 + 5103*u^7*v^6 + 5103*u^7*v^5 + 2835*u^7*v^4 + 945*u^7*v^3 + 189*u^7*v^2 +
21*u^7*v + u^7 + 5103*u^6*v^7 - 10206*u^6*v^6*z + 10206*u^6*v^6 - 20412*u^6*v^5*z +
8505*u^6*v^5 - 17010*u^6*v^4*z + 3780*u^6*v^4 - 7560*u^6*v^3*z + 945*u^6*v^3 -

1890*u^6*v^2*z + 126*u^6*v^2 - 252*u^6*v*z + 7*u^6*v - 14*u^6*z + 5103*u^5*v^7 -
20412*u^5*v^6*z + 8505*u^5*v^6 + 20412*u^5*v^5*z^2 - 34020*u^5*v^5*z + 5670*u^5*v^5 +
34020*u^5*v^4*z^2 - 22680*u^5*v^4*z + 1890*u^5*v^4 + 22680*u^5*v^3*z^2 - 7560*u^5*v^3*z +
315*u^5*v^3 + 7560*u^5*v^2*z^2 - 1260*u^5*v^2*z + 21*u^5*v^2 + 1260*u^5*v*z^2 - 84*u^5*v*z +
84*u^5*z^2 + 2835*u^4*v^7 - 17010*u^4*v^6*z + 3780*u^4*v^6 + 34020*u^4*v^5*z^2 -
22680*u^4*v^5*z + 1890*u^4*v^5 - 22680*u^4*v^4*z^3 + 45360*u^4*v^4*z^2 - 11340*u^4*v^4*z +
420*u^4*v^4 - 30240*u^4*v^3*z^3 + 22680*u^4*v^3*z^2 - 2520*u^4*v^3*z + 35*u^4*v^3 -
15120*u^4*v^2*z^3 + 5040*u^4*v^2*z^2 - 210*u^4*v^2*z - 3360*u^4*v*z^3 + 420*u^4*v*z^2 -
280*u^4*z^3 + 945*u^3*v^7 - 7560*u^3*v^6*z + 945*u^3*v^6 + 22680*u^3*v^5*z^2 -
7560*u^3*v^5*z + 315*u^3*v^5 - 30240*u^3*v^4*z^3 + 22680*u^3*v^4*z^2 - 2520*u^3*v^4*z +
35*u^3*v^4 + 15120*u^3*v^3*z^4 - 30240*u^3*v^3*z^3 + 7560*u^3*v^3*z^2 - 280*u^3*v^3*z +
15120*u^3*v^2*z^4 - 10080*u^3*v^2*z^3 + 840*u^3*v^2*z^2 + 5040*u^3*v*z^4 - 1120*u^3*v*z^3 +
560*u^3*z^4 + 189*u^2*v^7 - 1890*u^2*v^6*z + 126*u^2*v^6 + 7560*u^2*v^5*z^2 - 1260*u^2*v^5*z
+ 21*u^2*v^5 - 15120*u^2*v^4*z^3 + 5040*u^2*v^4*z^2 - 210*u^2*v^4*z + 15120*u^2*v^3*z^4 -
10080*u^2*v^3*z^3 + 840*u^2*v^3*z^2 - 6048*u^2*v^2*z^5 + 10080*u^2*v^2*z^4 -
1680*u^2*v^2*z^3 - 4032*u^2*v*z^5 + 1680*u^2*v*z^4 - 672*u^2*z^5 + 21*u*v^7 - 252*u*v^6*z +
7*u*v^6 + 1260*u*v^5*z^2 - 84*u*v^5*z - 3360*u*v^4*z^3 + 420*u*v^4*z^2 + 5040*u*v^3*z^4 -
1120*u*v^3*z^3 - 4032*u*v^2*z^5 + 1680*u*v^2*z^4 + 1344*u*v*z^6 - 1344*u*v*z^5 + 448*u*z^6 +
v^7 - 14*v^6*z + 84*v^5*z^2 - 280*v^4*z^3 + 560*v^3*z^4 - 672*v^2*z^5 + 448*v*z^6 - 128*z^7
Finally
coefficient of u2 v3 z3 ∈ ( 3 uv−2 z+u+ v )7 is-10080
Solution 3 :
Let S be a set with three distinguished elements a, b, and c and count certain k-subsets of S .
The number of k-subsets of S can be taken as (n
k )
Also the number of k-subsets of S - { a , b , c } is ( n−3
k )
Then the LHS is the number of k-subsets of S that contains at least of the elements of {a, b, c}.
Such k-subsets can be divided into 3 types :
(i) the k-subsets that contain the element a.
(ii) the k-subsets that do not contain a but contain b.
(iii) the k-subsets that do not contain a, b but contain c.

The numbers k-subsets of type (i), type (ii), type (iii) are
( n−1
k−1 ) , ( n−2
k−1 ) , ( n−3
k −1 )
( n
k ) −
( n−3
k )= ( n−1
k −1 ) + ( n−2
k −1 ) + ( n−3
k −1 )
Hence proved
Solution 4 :
To prove
∑
k =1
n
(n
k )( n
k−1 )= (2 n+2
n+1 )
2 −(2 n
n )
LHS:
∑
k =1
n
(n
k )( n
k−1 )
As
( n
k ) =
( n
k−1 )
So
∑
k =1
n
(n
k )2
¿−
( 2 n
n ) ( n
n+1 )
2
RHS:

( 2 n+2
n+1 )
2 −
( 2 n
n )
1
2 (2 n+2
n+ 1 )− (2 n
n )
1
2
( 2n+ 2 ) !
( n+1 ) ! ( n+ 1 ) ! − ( 2 n ) !
( n ) ! ( n ) !
1
n !n! ( 1
2
( 2 n+2 ) !
( n+1 ) ( n+1 ) − ( 2 n ) !
1 )
1
n ! n! ( 1
2
( 2 n+2 ) ( 2 n+1 ) 2 n !
( n+1 ) ( n+1 ) − ( 2 n ) !
1 )
2 n !
n ! n! (1
2
2 (2n+ 1)
( n+1 ) ( n+1 ) −1 )
2 n !
n ! n! ( (2 n+1)
( n+1 ) ( n+ 1 ) −1 )
2 n !
n ! n! (2 n+1−n2−1−2n
( n+1 )2 )
¿ 2 n !
n! n! ( −n2
( n+ 1 )2 )
¿ 2 n !
n! n! ( n
n+ 1 )2
¿−( 2 n
n ) ( n
n+1 )
2
Hence LHS=RHS
Solution 5

Solution 6 :
Given that
0, 0, 0, 0, 6, -6, 6, -6, 6, -6, . . …….
Assume the generating function
f ( x ) =a0 +a1 x+ a2 x2 +a3 x3 +a4 x4 + ¿…………………………………………….
But, the given sequence is {0, 0, 0, 0, 6, -6, 6, -6, 6, -6……}. Using this sequence, the expression above
becomes,
f ( x )=0+0 x+ 0 x2 +0 x3 +6 x4−6 x5 +¿……………………………………..
= 0 +0 + 0 + 0 + 6 x4 −6 x5 + ……………………………….
= 6 x4 −6 x5
= 6 x4 ¿
= Accordingly, f ( x )= 6 x4 ¿is the generating function for the given sequence {0, 0, 0, 0, 6, -6, 6, -6, 6, -
6……}.

Solution 7 :
Now
By induction assume
1+ 1
√ 2 + 1
3 + 1
√ 4 +… ..+ 1
√ n > 2 ( √ n+1−1 ) … … … … … … .(1)
1+ 1
√2 + 1
3 + 1
√4 +… ..+ 1
√n + 1
√n+1 > 2 ( √n+1−1 ) + 1
√n+1
So if we proves
1+ 1
√2 + 1
3 + 1
√4 +… ..+ 1
√n + 1
√n+1 > 2 ( √n+1−1 ) + 1
√n+1
1+ 1
√2 + 1
3 + 1
√4 +… ..+ 1
√n + 1
√ n+1 > 2 ( n+ 1− √n+1 ) +1
From 1 by substitution
2 ( √n+2−1 ) > ( 2 n+3− √n+1 )
2 ( √ n+2 ) > ( 2 n+5− √ n+1 )
( 2 n+3 ) 2 > 4(n2+3 n+ 2)
Hence our identity holds for (1)
Same is true for
1+ 1
√ 2 + 1
3 + 1
√ 4 +… ..+ 1
√ n < 2 ( √ n )
Hence we have prove
Solution 8 :
Using binomial theoerem we can have

( x + y )n=∑
k=0
n
(n
k ) xn−k yk
Now as we have
∑
i=1
n
i4 = n(n+1)(2 n+1)(3 n3 +3 n−1)
30
∑
i=1
n
i5= ( 1
6 )n6 + ( 1
2 )n5+ ( 5
12 )n4 −( 1
12 )n2
Solution 9
According to Multinomial theorem ,
Total powers sum is 4.
(a+ b+c )4 = ( 4
4 0 0 ) a4 +
( 4
3 1 0 ) a3 b1 +¿ …………………….. + ( 4
0 0 4 )c4
a4 +4 a3 b+ 4 a3 c +6 a2 b2 +6 a2 c2 +12 a2 bc+4 a b3+ ¿12
12 a b2 c+ 12abc2 +4 a c3 +b4 + 4 b3 c+6 b2 c2 + 4 b c3+c4
Solution 10 :
D, I ,S, C, R, E ,T ,E ,M ,A, T, H, E,, M ,A ,T ,I C ,S ,I, S, R, E, A, L ,L, Y ,F ,U ,N consist of
{E4,A3,I3,S3,T3,C2,L2,M2,R2,D,F,H,N,U,Y}
Total distinct ways to arrange the letters = ( 4+3 × 4+2 × 4+ 6) !
4 ! 3!4 2!4 1!4 =
532995876358730104320000000
All these words don't appear consecutively, in that
order 532995876358730104319999999 ways