Sequences, Series, and the Binomial Theorem

Study Sheet

Sequences, Series, and the Binomial Theorem

Explicit & recursive formulas, factorials, sigma notation, arithmetic & geometric series, induction, the Binomial Theorem, counting, and probability

Sequences: Explicit & Recursive Formulas, Factorials

Concept
Sequences and factorial notation

A sequence is a function whose domain is the positive integers. Its outputs a1,a2,a3,…a_1,a_2,a_3,\dots are the terms, and ana_n is the nnth (general) term.

  • [leftmargin=5mm]
  • Explicit formula: ana_n is given directly as a formula in nn. To list terms, substitute n=1,2,3,…n=1,2,3,\dots
  • Recursive formula: a starting term (or terms) plus a rule that builds each term from earlier ones, e.g. a1=3, an=an−1+4a_1=3,\ a_n=a_{n-1}+4.
  • Factorial: n!=n(n−1)(n−2)⋯2⋅1n!=n(n-1)(n-2)\cdots 2\cdot 1, and by definition 0!=10!=1. So 5!=1205!=120.
  • Simplifying factorials: cancel! 8!6!=8⋅7⋅6!6!=8⋅7=56\dfrac{8!}{6!}=\dfrac{8\cdot 7\cdot 6!}{6!}=8\cdot 7=56.
Example
Listing terms from a formula

Write the first four terms of an=(−1)n nn+1a_n=\dfrac{(-1)^n\, n}{n+1}.

a1=−12a_1=\dfrac{-1}{2},   a2=23a_2=\dfrac{2}{3},   a3=−34a_3=\dfrac{-3}{4},   a4=45a_4=\dfrac{4}{5}.

The factor (−1)n(-1)^n makes the signs alternate, starting negative.

Example
From recursive to terms

Let a1=2a_1=2 and an=3an−1−1a_n=3a_{n-1}-1. Find a2,a3,a4a_2,a_3,a_4.

a2=3(2)−1=5,a3=3(5)−1=14,a4=3(14)−1=41.a_2=3(2)-1=5,\quad a_3=3(5)-1=14,\quad a_4=3(14)-1=41.

Tip

Tip: A factorial in a denominator is your friend---always cancel the largest common factorial before multiplying. Never multiply out 8!8! if a 6!6! will cancel.

Summation (Sigma) Notation & Its Properties

Concept
Sigma notation

The sum of terms aka_k from k=1k=1 to nn is written

∑k=1nak=a1+a2+⋯+an.\sum_{k=1}^{n} a_k = a_1+a_2+\cdots+a_n .

Here kk is the index, 11 the lower limit, nn the upper limit. Useful properties:

∑k=1nc ak=c∑k=1nak,∑k=1n(ak±bk)=∑k=1nak±∑k=1nbk,∑k=1nc=cn.\sum_{k=1}^{n} c\,a_k = c\sum_{k=1}^{n} a_k,\qquad \sum_{k=1}^{n}(a_k\pm b_k)=\sum_{k=1}^{n}a_k\pm\sum_{k=1}^{n}b_k,\qquad \sum_{k=1}^{n} c = cn .

Handy closed forms:

∑k=1nk=n(n+1)2,∑k=1nk2=n(n+1)(2n+1)6,∑k=1nk3=[n(n+1)2]2.\sum_{k=1}^{n} k=\frac{n(n+1)}{2},\qquad \sum_{k=1}^{n} k^2=\frac{n(n+1)(2n+1)}{6},\qquad \sum_{k=1}^{n} k^3=\left[\frac{n(n+1)}{2}\right]^2 .
Example
Evaluating a sum with properties

Evaluate ∑k=15(2k+3)\displaystyle\sum_{k=1}^{5}(2k+3).

∑k=15(2k+3)=2∑k=15k+∑k=153=2⋅5⋅62+3⋅5=30+15=45.\displaystyle\sum_{k=1}^{5}(2k+3)=2\sum_{k=1}^{5}k+\sum_{k=1}^{5}3 =2\cdot\frac{5\cdot 6}{2}+3\cdot 5=30+15=45.

Check by hand: 5+7+9+11+13=45.5+7+9+11+13=45. ✓

Tip

Tip: ∑k=1nc=cn\sum_{k=1}^{n} c = cn, not cc. A constant is added once for every value of the index.

Arithmetic Sequences and Partial Sums

Concept
Arithmetic sequences

An arithmetic sequence adds a fixed common difference dd each step, so d=an−an−1d=a_{n}-a_{n-1}.

nth term:an=a1+(n−1)d.\textbf{$n$th term:}\quad a_n=a_1+(n-1)d.

The sum of the first nn terms (an arithmetic series) is

Sn=n2(a1+an)=n2[ 2a1+(n−1)d ].S_n=\frac{n}{2}\big(a_1+a_n\big)=\frac{n}{2}\big[\,2a_1+(n-1)d\,\big].
Example
Finding a term and a sum

For 3,7,11,15,…3,7,11,15,\dots find a20a_{20} and S20S_{20}.

Here a1=3a_1=3, d=4d=4.   a20=3+(20−1)(4)=3+76=79.a_{20}=3+(20-1)(4)=3+76=79.

S20=202(a1+a20)=10(3+79)=10(82)=820.S_{20}=\dfrac{20}{2}(a_1+a_{20})=10(3+79)=10(82)=820.

Tip

Tip: It is (n−1)d(n-1)d, not ndnd. The first term already “used up” zero steps, so the nnth term has taken only n−1n-1 steps of size dd.

Geometric Sequences & Series (incl. Infinite)

Concept
Geometric sequences and series

A geometric sequence multiplies by a fixed common ratio rr each step, so r=anan−1r=\dfrac{a_n}{a_{n-1}}.

nth term:an=a1 r n−1.\textbf{$n$th term:}\quad a_n=a_1\,r^{\,n-1}.

Finite sum of the first nn terms:

Sn=a1⋅1−r n1−r(r≠1).S_n=a_1\cdot\frac{1-r^{\,n}}{1-r}\qquad(r\ne 1).

Infinite geometric series: if ∣r∣<1|r|<1 the partial sums converge and

S=∑k=1∞a1r k−1=a11−r.S=\sum_{k=1}^{\infty} a_1 r^{\,k-1}=\frac{a_1}{1-r}.

If ∣r∣≥1|r|\ge 1 the series diverges (no finite sum).

Example
Finite geometric sum

Sum the first 66 terms of 2,6,18,54,…2,6,18,54,\dots

Here a1=2a_1=2, r=3r=3.   S6=2⋅1−361−3=2⋅1−729−2=2⋅−728−2=728.S_6=2\cdot\dfrac{1-3^{6}}{1-3}=2\cdot\dfrac{1-729}{-2}=2\cdot\dfrac{-728}{-2}=728.

Example
Infinite geometric series

Evaluate ∑k=1∞5(23)k−1\displaystyle\sum_{k=1}^{\infty} 5\left(\tfrac{2}{3}\right)^{k-1}.

Here a1=5a_1=5 and r=23r=\tfrac{2}{3}, and ∣r∣<1|r|<1, so it converges:

S=a11−r=51−23=513=15.S=\frac{a_1}{1-r}=\frac{5}{1-\frac{2}{3}}=\frac{5}{\frac{1}{3}}=15.
Tip

Tip: Only check convergence with ∣r∣<1|r|<1. A repeating decimal such as 0.7‾=710+7100+⋯0.\overline{7}=\frac{7}{10}+\frac{7}{100}+\cdots is an infinite geometric series with a1=710a_1=\frac{7}{10}, r=110r=\frac{1}{10}, giving 7/109/10=79\frac{7/10}{9/10}=\frac{7}{9}.

Mathematical Induction

Concept
The principle of induction

To prove a statement P(n)P(n) holds for every positive integer nn:

  • [leftmargin=6mm]
  • Base case: verify P(1)P(1) is true.
  • Inductive step: assume P(k)P(k) is true (the inductive hypothesis) and use it to prove P(k+1)P(k+1).

Then P(n)P(n) is true for all n≥1n\ge 1.

Example
A full induction proof of a summation formula

Prove that ∑k=1nk=n(n+1)2\displaystyle\sum_{k=1}^{n} k=\frac{n(n+1)}{2} for all integers n≥1n\ge 1.

Base case (n=1n=1): the left side is 11; the right side is 1(1+1)2=1\dfrac{1(1+1)}{2}=1. They agree. ✓

Inductive step: assume ∑k=1mk=m(m+1)2\displaystyle\sum_{k=1}^{m} k=\frac{m(m+1)}{2} for some integer m≥1m\ge 1. We must show the formula holds for m+1m+1:

∑k=1m+1k=(∑k=1mk)+(m+1)=m(m+1)2+(m+1).\sum_{k=1}^{m+1} k=\left(\sum_{k=1}^{m} k\right)+(m+1) =\frac{m(m+1)}{2}+(m+1).

Factor out (m+1)(m+1):

=(m+1) ⁣(m2+1)=(m+1)⋅m+22=(m+1)((m+1)+1)2.=(m+1)\!\left(\frac{m}{2}+1\right)=(m+1)\cdot\frac{m+2}{2}=\frac{(m+1)\big((m+1)+1\big)}{2}.

This is exactly the formula with n=m+1n=m+1. By induction the statement holds for all n≥1n\ge 1. ■\blacksquare

Tip

Tip: In the inductive step, always start from ∑k=1m+1=(∑k=1m)+am+1\sum_{k=1}^{m+1}=\big(\sum_{k=1}^{m}\big)+a_{m+1}, replace the bracket using the hypothesis, then algebra should rebuild the formula with n=m+1n=m+1.

The Binomial Theorem & Pascal's Triangle

Concept
Binomial coefficients and the theorem

The binomial coefficient is

(nk)=n!k! (n−k)!,(n0)=(nn)=1.\binom{n}{k}=\frac{n!}{k!\,(n-k)!},\qquad \binom{n}{0}=\binom{n}{n}=1 .

The Binomial Theorem expands a power of a binomial:

(x+y)n=∑k=0n(nk)x n−ky k=(n0)xn+(n1)xn−1y+⋯+(nn)yn.(x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^{\,n-k}y^{\,k} =\binom{n}{0}x^n+\binom{n}{1}x^{n-1}y+\cdots+\binom{n}{n}y^n .

The (k+1)(k+1)st term of the expansion is (nk)x n−ky k\displaystyle\binom{n}{k}x^{\,n-k}y^{\,k}.

Pascal's triangle gives the coefficients; each entry is the sum of the two above it:

111121133114641\begin{array}{ccccccccc} & & & & 1 & & & &\\ & & & 1 & & 1 & & &\\ & & 1 & & 2 & & 1 & &\\ & 1 & & 3 & & 3 & & 1 &\\ 1 & & 4 & & 6 & & 4 & & 1 \end{array}
Reminder — The binomial theorem:  (x+y)n=∑k=0n(nk)x n−kyk(x+y)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{\,n-k}y^{k}
Example
A full binomial expansion

Expand (x+2)4(x+2)^4.

Row of coefficients: 1,4,6,4,11,4,6,4,1. With y=2y=2:

(x+2)4=(40)x4+(41)x3(2)+(42)x2(22)+(43)x(23)+(44)(24).(x+2)^4=\binom{4}{0}x^4+\binom{4}{1}x^3(2)+\binom{4}{2}x^2(2^2)+\binom{4}{3}x(2^3)+\binom{4}{4}(2^4).
=x4+4x3(2)+6x2(4)+4x(8)+16=x4+8x3+24x2+32x+16.=x^4+4x^3(2)+6x^2(4)+4x(8)+16=x^4+8x^3+24x^2+32x+16.
Example
Finding a specific term

Find the term containing x4x^4 in (2x−1)6(2x-1)^6.

General term: (6k)(2x)6−k(−1)k\displaystyle\binom{6}{k}(2x)^{6-k}(-1)^{k}. We need power 6−k=46-k=4, so k=2k=2:

(62)(2x)4(−1)2=15⋅16x4⋅1=240x4.\binom{6}{2}(2x)^{4}(-1)^{2}=15\cdot 16x^4\cdot 1=240x^4 .

The coefficient of x4x^4 is 240240.

Tip

Tip: The (k+1)(k+1)st term uses index kk, and the exponents on xx and yy always add to nn. When a term has a coefficient like 2x2x or a sign like −1-1, raise the whole thing to its power.

Counting Principles: FCP, Permutations, Combinations

Concept
Three counting tools
  • [leftmargin=5mm]
  • Fundamental Counting Principle (FCP): if a task is done in stages with m1,m2,…m_1,m_2,\dots choices, the total number of outcomes is m1⋅m2⋯m_1\cdot m_2\cdots.
  • Permutations (order matters): number of ways to arrange rr of nn objects is @@BLOCK0@@
  • Combinations (order does not matter): number of ways to choose rr of nn objects is @@BLOCK1@@
Example
Permutation vs. combination

From 1010 students, (a) how many ways to pick a president then a vice-president? (b) how many ways to pick a 22-person committee?

(a) Order matters: 10P2=10!8!=10⋅9=90.{}_{10}P_2=\dfrac{10!}{8!}=10\cdot 9=90.

(b) Order does not matter: 10C2=(102)=10⋅92⋅1=45.{}_{10}C_2=\dbinom{10}{2}=\dfrac{10\cdot 9}{2\cdot 1}=45.

Tip

Tip: Ask “does swapping two chosen items give a different outcome?” If yes, use a permutation; if no, use a combination. Note nPr=r!⋅nCr{}_nP_r=r!\cdot{}_nC_r.

Probability Using Counting

Concept
Basic probability

For equally likely outcomes,

P(E)=number of favorable outcomestotal number of outcomes=n(E)n(S).P(E)=\frac{\text{number of favorable outcomes}}{\text{total number of outcomes}}=\frac{n(E)}{n(S)} .

Always 0≤P(E)≤10\le P(E)\le 1. The complement satisfies P(not E)=1−P(E)P(\text{not }E)=1-P(E). Use combinations to count favorable and total outcomes when order does not matter.

Example
Probability with combinations

A bag has 55 red and 33 blue marbles. Two are drawn at random. Find P(both red)P(\text{both red}).

Total ways to choose 22 of 88: (82)=28.\dbinom{8}{2}=28.   Favorable (both red): (52)=10.\dbinom{5}{2}=10.

P(both red)=1028=514.P(\text{both red})=\frac{10}{28}=\frac{5}{14}.
Tip

Tip: When “at least one” appears, the complement is usually faster: P(at least one)=1−P(none)P(\text{at least one})=1-P(\text{none}).

Going Deeper: Advanced Sequences, Series & Binomial

Concept
Telescoping sums via partial fractions

A sum telescopes when each term splits into a difference so that interior terms cancel in pairs. The key tool is a partial-fraction split. For a product of consecutive linear factors,

1k(k+1)=1k−1k+1,1k(k+2)=12 ⁣(1k−1k+2).\frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1},\qquad \frac{1}{k(k+2)}=\frac{1}{2}\!\left(\frac{1}{k}-\frac{1}{k+2}\right).

Once written as tk=bk−bk+1t_k=b_k-b_{k+1}, the partial sum collapses:

∑k=1n(bk−bk+1)=b1−bn+1.\sum_{k=1}^{n}\big(b_k-b_{k+1}\big)=b_1-b_{n+1}.

Only the first surviving piece and the last surviving piece remain.

Example
A telescoping series (worked)

Evaluate ∑k=1n1k(k+1)\displaystyle\sum_{k=1}^{n}\frac{1}{k(k+1)} and then take n→∞n\to\infty.

Split each term: 1k(k+1)=1k−1k+1\dfrac{1}{k(k+1)}=\dfrac{1}{k}-\dfrac{1}{k+1}. Then

∑k=1n(1k−1k+1)=(1−12)+(12−13)+⋯+(1n−1n+1)=1−1n+1=nn+1.\sum_{k=1}^{n}\left(\frac{1}{k}-\frac{1}{k+1}\right) =\left(1-\frac{1}{2}\right)+\left(\frac{1}{2}-\frac{1}{3}\right)+\cdots+\left(\frac{1}{n}-\frac{1}{n+1}\right) =1-\frac{1}{n+1}=\frac{n}{n+1}.

As n→∞n\to\infty, 1n+1→0\dfrac{1}{n+1}\to 0, so the infinite sum is ∑k=1∞1k(k+1)=1.\displaystyle\sum_{k=1}^{\infty}\frac{1}{k(k+1)}=1.

Concept
Weighted geometric sums: ∑k r k\sum k\,r^{\,k}

The plain geometric sum has a closed form; multiplying each term by kk needs one extra idea. For ∣r∣<1|r|<1 the infinite weighted sum converges to

∑k=1∞k r k=r(1−r)2(∣r∣<1).\sum_{k=1}^{\infty} k\,r^{\,k}=\frac{r}{(1-r)^2}\qquad(|r|<1).

Why (difference trick): let S=∑k=1nk rkS=\sum_{k=1}^{n} k\,r^{k}. Form S−rSS-rS; each column telescopes so that

(1−r)S=(r+r2+⋯+rn)−n r n+1=r(1−rn)1−r−n r n+1.(1-r)S=\big(r+r^2+\cdots+r^{n}\big)-n\,r^{\,n+1} = \frac{r(1-r^{n})}{1-r}-n\,r^{\,n+1}.

When ∣r∣<1|r|<1 the terms rnr^{n} and nr n+1→0n r^{\,n+1}\to 0, leaving S=r(1−r)2S=\dfrac{r}{(1-r)^2}. Compare with the pure power sum ∑k=1nk2=n(n+1)(2n+1)6\sum_{k=1}^{n}k^2=\dfrac{n(n+1)(2n+1)}{6}, which grows without bound (it has no infinite value).

Example
Computing ∑k rk\sum k\,r^{k} and ∑k2\sum k^2 (worked)

(a) Evaluate ∑k=1∞k(12)k\displaystyle\sum_{k=1}^{\infty} k\left(\tfrac{1}{2}\right)^{k}.

Here r=12r=\tfrac12 and ∣r∣<1|r|<1, so

∑k=1∞k(12)k=r(1−r)2=12(12)2=1214=2.\sum_{k=1}^{\infty} k\left(\tfrac12\right)^{k}=\frac{r}{(1-r)^2}=\frac{\tfrac12}{\left(\tfrac12\right)^2}=\frac{\tfrac12}{\tfrac14}=2.

(b) Evaluate ∑k=110k2\displaystyle\sum_{k=1}^{10} k^2 with the closed form:

∑k=110k2=10⋅11⋅216=23106=385.\sum_{k=1}^{10} k^2=\frac{10\cdot 11\cdot 21}{6}=\frac{2310}{6}=385.
Concept
Solving a linear recurrence for a closed form

A first-order recurrence an=r an−1+ca_n=r\,a_{n-1}+c (with r≠1r\ne 1) can be turned into an explicit formula. Find the fixed point L=c1−rL=\dfrac{c}{1-r} (solve L=rL+cL=rL+c); then the shifted sequence an−La_n-L is purely geometric:

an−L=r (an−1−L) ⟹ an=L+(a1−L) r n−1.a_n-L=r\,(a_{n-1}-L)\ \Longrightarrow\ a_n=L+(a_1-L)\,r^{\,n-1}.

This converts a step-by-step rule into a formula you can evaluate directly at any nn.

Example
Recurrence to closed form (worked)

Solve a1=2, an=3an−1−1a_1=2,\ a_n=3a_{n-1}-1 for an explicit formula, and check against the earlier hand-computed terms 2,5,14,412,5,14,41.

Fixed point: L=3L−1⇒L=12L=3L-1\Rightarrow L=\tfrac12. So an−12=3(an−1−12)a_n-\tfrac12=3\big(a_{n-1}-\tfrac12\big), a geometric sequence with ratio 33 and first term a1−12=32a_1-\tfrac12=\tfrac32:

an=12+32⋅3 n−1=1+3 n2.a_n=\frac12+\frac32\cdot 3^{\,n-1}=\frac{1+3^{\,n}}{2}.

Check: a1=1+32=2a_1=\tfrac{1+3}{2}=2, a2=1+92=5a_2=\tfrac{1+9}{2}=5, a3=1+272=14a_3=\tfrac{1+27}{2}=14, a4=1+812=41.a_4=\tfrac{1+81}{2}=41. ✓

Concept
Binomial-coefficient identities

These follow from the Binomial Theorem and from Pascal's rule (nk)=(n−1k−1)+(n−1k)\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}:

  • [leftmargin=5mm]
  • Row sum: setting x=y=1x=y=1 in (x+y)n(x+y)^n gives ∑k=0n(nk)=2 n\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^{\,n}.
  • Alternating sum: setting x=1, y=−1x=1,\ y=-1 gives ∑k=0n(−1)k(nk)=0\displaystyle\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0 (for n≥1n\ge 1).
  • Weighted sum: ∑k=0nk(nk)=n 2 n−1\displaystyle\sum_{k=0}^{n} k\binom{n}{k}=n\,2^{\,n-1}, using k(nk)=n(n−1k−1)k\binom{n}{k}=n\binom{n-1}{k-1}.
  • Hockey-stick: ∑i=rn(ir)=(n+1r+1)\displaystyle\sum_{i=r}^{n}\binom{i}{r}=\binom{n+1}{r+1} --- a diagonal of Pascal's triangle sums to the entry just below its end.
Example
Using the identities (worked)

(a) A pizza shop offers 66 toppings. How many topping-subsets are possible (including plain)?

Choose any subset: ∑k=06(6k)=26=64.\displaystyle\sum_{k=0}^{6}\binom{6}{k}=2^{6}=64.

(b) Verify the hockey-stick identity ∑i=25(i2)=(63)\displaystyle\sum_{i=2}^{5}\binom{i}{2}=\binom{6}{3}.

Left: (22)+(32)+(42)+(52)=1+3+6+10=20\binom{2}{2}+\binom{3}{2}+\binom{4}{2}+\binom{5}{2}=1+3+6+10=20. Right: (63)=20.\binom{6}{3}=20. ✓

Example
Induction proof of the row-sum identity

Prove ∑k=0n(nk)=2 n\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^{\,n} for all integers n≥0n\ge 0.

Base case (n=0n=0): the left side is (00)=1\binom{0}{0}=1 and the right side is 20=12^0=1. They agree. ✓

Inductive step: assume ∑k=0m(mk)=2 m\displaystyle\sum_{k=0}^{m}\binom{m}{k}=2^{\,m}. Using Pascal's rule (m+1k)=(mk−1)+(mk)\binom{m+1}{k}=\binom{m}{k-1}+\binom{m}{k} (with (m−1)=(mm+1)=0\binom{m}{-1}=\binom{m}{m+1}=0),

∑k=0m+1(m+1k)=∑k=0m+1(mk−1)+∑k=0m+1(mk)=∑k=0m(mk)⏟2m+∑k=0m(mk)⏟2m=2m+2m=2 m+1.\sum_{k=0}^{m+1}\binom{m+1}{k} =\sum_{k=0}^{m+1}\binom{m}{k-1}+\sum_{k=0}^{m+1}\binom{m}{k} =\underbrace{\sum_{k=0}^{m}\binom{m}{k}}_{2^{m}}+\underbrace{\sum_{k=0}^{m}\binom{m}{k}}_{2^{m}} =2^{m}+2^{m}=2^{\,m+1}.

This is the formula with n=m+1n=m+1. By induction it holds for all n≥0n\ge 0. ■\blacksquare

Concept
Generating-function-flavored counting

A product of binomials is a bookkeeping device: the coefficient of a power records how many ways to reach it. Since (1+x)n=∑k(nk)xk(1+x)^n=\sum_{k}\binom{n}{k}x^k, the coefficient of xkx^k counts the ways to choose kk items from nn. Multiplying expansions combines independent choices, and Vandermonde's identity

(m+nr)=∑k=0r(mk)(nr−k)\binom{m+n}{r}=\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}

comes from matching the xrx^r coefficient on both sides of (1+x)m(1+x)n=(1+x)m+n(1+x)^m(1+x)^n=(1+x)^{m+n}.

Example
Extracting a specific term from a product

Find the coefficient of x2x^{2} in (1+x)3(1+x)4(1+x)^{3}(1+x)^{4}.

The product is (1+x)7(1+x)^{7}, so the coefficient of x2x^2 is (72)=21\binom{7}{2}=21. As a Vandermonde check with m=3,n=4,r=2m=3,n=4,r=2:

∑k=02(3k)(42−k)=(30)(42)+(31)(41)+(32)(40)=6+12+3=21. ✓\sum_{k=0}^{2}\binom{3}{k}\binom{4}{2-k}=\binom{3}{0}\binom{4}{2}+\binom{3}{1}\binom{4}{1}+\binom{3}{2}\binom{4}{0}=6+12+3=21.\ \checkmark
Example
A constant-term extraction (worked)

Find the constant term in (2x+1x)6\left(2x+\dfrac{1}{x}\right)^{6}.

General term: (6k)(2x)6−k ⁣(1x)k=(6k)2 6−k x 6−2k\displaystyle\binom{6}{k}(2x)^{6-k}\!\left(\frac{1}{x}\right)^{k}=\binom{6}{k}2^{\,6-k}\,x^{\,6-2k}. The constant term needs 6−2k=06-2k=0, so k=3k=3:

(63)2 3x0=20⋅8=160.\binom{6}{3}2^{\,3}x^{0}=20\cdot 8=160.

The constant term is 160160.

Tip

Tips for the advanced toolkit: (1) Before any infinite sum, confirm convergence---geometric-type sums need ∣r∣<1|r|<1. (2) To spot a telescoping sum, try a partial-fraction split and look for a bk−bk+1b_k-b_{k+1} pattern. (3) For “specific term” problems, write the general term first, set the exponent equal to the target, solve for kk, then substitute. (4) Many binomial identities are just the Binomial Theorem with a clever choice of xx and yy.

Formulas, Proofs & Tips

Tip
Arithmetic sequences and series
an=a1+(n−1)d,Sn=n2(a1+an)a_n=a_1+(n-1)d,\qquad S_n=\frac{n}{2}\left(a_1+a_n\right)

What it means. A constant is added each step; the sum is the number of terms times the average of the first and last.

Example. 3,7,11,…3,7,11,\dots: a5=3+4⋅4=19a_5=3+4\cdot 4=19 and S5=52(3+19)=55S_5=\tfrac52(3+19)=55.

Why it works. Getting to the nnth term takes n−1n-1 steps of size dd. For the sum, write SnS_n forwards and backwards and add: every column totals a1+ana_1+a_n, and there are nn columns, giving 2Sn=n(a1+an)2S_n=n(a_1+a_n).

Tip. It is n−1n-1, not nn — the first term takes no steps. Check with n=1n=1.

Tip
Geometric sequences and series
an=a1r n−1,Sn=a11−rn1−r,S∞=a11−r  (∣r∣<1)a_n=a_1r^{\,n-1},\qquad S_n=a_1\frac{1-r^{n}}{1-r},\qquad S_\infty=\frac{a_1}{1-r}\ \ (|r|<1)

What it means. A constant multiplier each step. If the ratio is small enough the infinite sum settles on a finite number.

Example. 2,6,18,…2,6,18,\dots: a4=2⋅33=54a_4=2\cdot 3^3=54 and S4=2⋅34−12=80S_4=2\cdot\tfrac{3^4-1}{2}=80.

Why it works. For the finite sum, subtract rSnrS_n from SnS_n: every middle term cancels, leaving Sn(1−r)=a1(1−rn)S_n(1-r)=a_1(1-r^{n}). When ∣r∣<1|r|<1, rn→0r^{n}\to 0 as nn grows, which collapses the numerator to 11.

Tip. The infinite formula needs ∣r∣<1|r|<1. If ∣r∣≥1|r|\ge 1 the terms do not shrink and the sum diverges.

Tip
The binomial theorem
(x+y)n=∑k=0n(nk)x n−kyk(x+y)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{\,n-k}y^{k}

What it means. Expands any power of a binomial; (nk)\binom{n}{k} is row nn of Pascal's triangle.

Example. (x+1)3=x3+3x2+3x+1(x+1)^3=x^3+3x^2+3x+1, the coefficients 1,3,3,11,3,3,1 being (3k)\binom3k.

Why it works. Expanding (x+y)n(x+y)^n means choosing, from each of the nn factors, either xx or yy. A term with kk copies of yy arises once for every way of choosing which kk factors supply the yy — that count is (nk)\binom{n}{k}.

Tip. The term containing yky^k is (nk)xn−kyk\binom{n}{k}x^{n-k}y^k, so you can grab a single coefficient without expanding everything.