Chapter 8: Mathematical Induction and Binomial Theorem

0 The Principle of Mathematical Induction has steps:

1 In inductive step, we assume P(k) true and prove:

2 The base case for induction usually shows P(n) true for:

3 Binomial theorem: (a+b)^n = Σ C(n,r) a^{n−r} b^r for r=0 to n. Valid for:

4 General term T_{r+1} in (a+b)^n =

5 Number of terms in expansion of (a+b)^n:

6 Sum of binomial coefficients in (1+x)^n:

7 Middle term of (a+b)^n when n is even:

8 Coefficient of x^r in (1+x)^n:

9 (1+x)^n expanded up to x^2 ≈

10 Pascal's triangle: each element is the sum of the:

11 Prove by induction: 1+2+...+n = n(n+1)/2. Base (n=1): LHS=1, RHS=

12 Inductive step: assume 1+...+k=k(k+1)/2. Add (k+1): LHS=

13 The Binomial coefficient C(n,r) is also written as:

14 In (2x+3)^5, the term with x^3 has r=

15 C(5,2)(2x)^3(3)^2 for (2x+3)^5 with r=2 gives coefficient:

16 4th term of (x+y)^7 (T_4, r=3):

17 Sum of coefficients of (2x+3)^n with x=1:

18 Prove 2^n > n for all n≥1 by induction. Base n=1: 2>1 ✓. Step: assume 2^k>k. Then 2^{k+1}=2×2^k >

19 The binomial expansion of (1−x)^n starts:

20 Coefficient of x^2 in (1+x)^8:

21 Middle term of (x+y)^6 (n=6, middle at r=3):

22 By induction: n³−n is divisible by 6 for all n∈N. Base n=1: 1−1=0, divisible by 6?

23 Binomial theorem for negative/fractional n gives:

24 Coefficient of x^3 in (1+x)^10:

25 Last term of (a+b)^n:

26 First term of (a+b)^n:

27 Telescoping sum: Σ(k=1 to n) k(k+1) proved by induction. T_n: n(n+1)(n+2)/3. Check n=1: 1×2=2, formula: 1×2×3/3=2. ✓

28 (a+b)^0 =

29 Σ_{k=0}^{n} (−1)^k C(n,k) =

30 Binomial coefficient C(n,r)+C(n,r+1) = C(n+1,r+1). This is:

31 Coefficient of x^4 in (1+2x)^10:

32 For PMI to work, the proposition must be:

33 Prove n^2+n is even for all n. Base: n=1: 1+1=2, even. ✓ Step: (k+1)^2+(k+1)=k^2+3k+2=

34 n! > 2^n for n≥?

35 Sum of odd binomial coefficients = Sum of even binomial coefficients for (1+1)^n:

36 T_{r+1} of (1+x)^n: if r=0 gives T_1=

37 The greatest coefficient in (1+x)^{2n} is:

38 PMI cannot prove statements that are:

39 (x+1/x)^6: term independent of x (T_{r+1} with x^{6-2r}=1, r=3):

40 Prove 1^3+2^3+...+n^3=[n(n+1)/2]^2. Note that [n(n+1)/2]^2 =

41 For large n, (1+1/n)^n approaches:

42 Coefficient of x^2y^3 in (x+y)^5:

43 Expand (1+x)^3 = ?

44 The sum Σ_{r=0}^n r×C(n,r) =

45 Last digit of 3^100 found using binomial: (3^4)^25=(81)^25=(80+1)^25; last digit:

46 The term containing y^4 in (x+y)^7 is:

47 PMI: "Strong induction" assumes P(1),P(2),...,P(k) all true to prove:

48 Coefficient of a^3b^3 in (a+b)^6:

49 (2+x)^3 coefficient of x^2:

50 Proof by induction that 4^n−1 is divisible by 3: 4^{k+1}−1=4×4^k−1=4(4^k−1)+3. The term 4(4^k−1) is div by 3 because:

51 (a−b)^4 = ?

52 Number of terms in (x+y+z)^n:

53 Σ_{r=0}^n C(n,r) × 3^r = (1+3)^n = ?

54 5th term of (a−b)^8 (T_5, r=4):

55 PMI base case for n=2 instead of n=1 proves the statement for:

56 (1+x)^{1/2} ≈ 1+(1/2)x for small x is:

57 Σ_{r=0}^n (−1)^r C(n,r) r = ?

58 C(n,r) is maximum when r = ?

59 In (1+x)^n, term T_3 (r=2) = ?

60 Coefficient of x^5 in (1+x)^{10}:

61 PMI: to prove Σk^2=n(n+1)(2n+1)/6, the inductive step adds:

62 The Binomial series (1+x)^n for |x|<1 and any real n is:

63 T_{r+1} of (2x−3)^5 with r=2:

64 Total number of terms in expansion (1+x)^{n} using PMI:

65 Proof: 2n < n! for n≥4. Base n=4: 8<24 ✓. Inductive step: 2(k+1)=2k+2<k!+2<(k+1)!

66 C(12,4) =

67 Which identity is Pascal's?

68 (x+2)^4 expansion: coefficient of x^2:

69 By induction: n(n+1) is always even. Because:

70 Σ_{r=0}^n C(n,r) = 128 means 2^n=128, so n=

71 Coefficient of x^4 in (x+1/x)^8 (term with x^{8-2r}=4, r=2):

72 PMI requires propositions about which type of numbers?

73 Alternate expression: C(n,r) = C(n−1,r) + ?

74 (a+b)^2 expanded:

75 (a−b)^2 expanded:

76 (a+b)^3 = ?

77 n^2 > n for n≥?

78 Coefficient of xy^3 in (x+y)^4:

79 Which power of 3 ends in digit 1?

80 The well-ordering principle (which underlies PMI) states every non-empty set of natural numbers has a:

81 C(2n,n) is:

82 T_{r+1} of (x^2 + 1/x)^9: term independent of x when 18-3r=0, r=?

83 4^3+5^3+6^3−(1^3+2^3+3^3)= (proved by telescoping/induction) =

84 Sum of first n terms of GP proved by induction: S_n=a(r^n−1)/(r−1). Verify n=1: S_1=a(r−1)/(r−1)=