Scribd
Upload
12 views1 page

PS11 DS

The document is a problem sheet focused on combinatorics and difference sequences, dated April 26, 2025. It includes various problems such as proving properties of difference sequences, finding specific functions, computing sums of sequences, and expressing functions as linear combinations of binomial coefficients. The problems require mathematical proofs and computations related to sequences and their differences.

Uploaded by

Buddhadev Mandal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views1 page

PS11 DS

The document is a problem sheet focused on combinatorics and difference sequences, dated April 26, 2025. It includes various problems such as proving properties of difference sequences, finding specific functions, computing sums of sequences, and expressing functions as linear combinations of binomial coefficients. The problems require mathematical proofs and computations related to sequences and their differences.

Uploaded by

Buddhadev Mandal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Combinatorics –Problem Sheet 10

Difference Sequences

26-April-2025

1. Prove the following properties for arbitrary constant C and functions f (n), g(n).

(a) ∆C = 0
(b) ∆(Cf (n)) = C∆f (n) and
(c) ∆(f (n) + g(n)) = ∆f (n) + ∆g(n)

2. Find all functions f (n) satisfying ∆(∆f (n)) = 3.

3. Let an be the sequence 3, 4, 9, 18, · · · defined by an+1 = an + 4n + 1, for n > 0 and a0 = 3.

(a) Compute a4 , a5 , · · · , a8 .
(b) Compute ∆an .
(c) Starting with a first row consisting of the nine numbers a0 , a1 , · · · , a8 , exhibit the rest
of the difference array for an .
(d) Prove that an = 2n2 − n + 3, for n ≥ 0. (e) Let bn be the sequence defined by bn = ∆an ,
n ≥ 0. Find a polynomial g such that bn = g(n) for all n ≥ 0.

4. Compute the sum of the first 100 numbers a0 + a1 + · · · + a99 of the arithmetic sequence that
begins with 7, 11, 15, · · ·

5. Let an be a sequence that satisfies ∆m+1 an = 0, for all n ≥ 0. Prove that the sum of the first
k numbers in the sequence is given by the formula
k−1 m
C(k, r + 1)∆r a0
X X
an =
n=0 r=0

and hence, evaluate the sum 12 + 22 + 32 + · · · + k 2 .

6. Use the technique of difference sequences to show that

S(n + 3, n) = C(n + 3, 4) + 10C(n + 3, 5) + 15C(n + 3, 6).

7. Use the theorem from class to express f (n) = 3n2 +2n+1 as a linear combination of binomial
coefficients.

You might also like