6D (Numbers and Sets)

For

0 \leq k \leq n

, the binomial coefficient is

(k n) = \frac{n !}{k ! ( n - k )!} .

(1)

When

1 \leq k \leq n - 1

(k n - 1) + (k - 1 n - 1) = \frac{( n - 1 )!}{k ! ( n - 1 - k )!} + \frac{( n - 1 )!}{( k - 1 )! ( n - k )!} = \frac{( n - 1 )! [( n - k ) + k ]}{k ! ( n - k )!} = (k n) .

(2)

This is Pascal's identity.

b

 0  0

Solution

 0  0

The special binomial theorem

(1 + t)^{n} = \sum_{k = 0}^{n} (k n) t^{k}

(1)

follows by mathematical induction. Multiplication of the formula for

n

1 + t

and collection of the coefficient of

t^{k}

uses Pascal's identity from part (a).

Termwise integration from

0

1

gives

k = 0 \sum n \frac{1}{k + 1} (k n) = \int_{0}^{1} (1 + t)^{n} d t = \frac{2 ^{n + 1} - 1}{n + 1} .

(2)

Replacing

t

- t

gives

k = 0 \sum n \frac{( - 1 ) ^{k}}{k + 1} (k n) = \int_{0}^{1} (1 - t)^{n} d t = \frac{1}{n + 1} .

(3)

Finally,

\sum_{k = 1}^{n} \frac{( - 1 ) ^{k + 1}}{k} (k n) = \int_{0}^{1} \frac{1 - ( 1 - x ) ^{n}}{x} d x .

(4)

Writing

y = 1 - x

and using the finite geometric series,

\frac{1 - y ^{n}}{1 - y} = 1 + y + \dots + y^{n - 1},

(5)

turns this into

j = 0 \sum n - 1 \int_{0}^{1} y^{j} d y = 1 + \frac{1}{2} + \dots + \frac{1}{n} .

(6)

c

 0  0

Solution

 0  0

Put

S_{n} = \sum_{k = 0}^{⌊(n - 1) /2 ⌋} (k n - k - 1) .

(1)

The initial values are

S_{1} = S_{2} = 1

. Using Pascal's identity and the convention that an out-of-range binomial coefficient is zero,

S_{n + 2} = k \geq 0 \sum (k n + 1 - k) = k \geq 0 \sum (k n - k) + k \geq 1 \sum (k - 1 n - k) = S_{n + 1} + S_{n} .

(2)

Thus

(S_{n})

has the same initial values and linear recurrence relation as the Fibonacci numbers. Mathematical induction gives

F_{n} = k = 0 \sum ⌊(n - 1) /2 ⌋ (k n - k - 1) .

(3)

 Ancestors (9)

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version

Past exam of the mathematics course of the University of Cambridge / 2022 / ia / Paper 4 / 6D (Numbers and Sets)

 Discussion (0)  Subscribe (1)

 Discussion (0)