Ch.2: Computation of Sums

From the lecture notes "Combinatorics, Graphs, Matroids" (University of Bonn, winter term 2025/26) 2.1. Sums: Direct Methods 2.2. Difference and Sum Operators 2.3. Inversions

64 flashcards · Mathematics · by lakesare

Part of University of Bonn › V3C2: Combinatorics, Graphs, Matroids · 6 courses

1. [Sums: Direct Methods] Arithmetic-geometric mean inequality: for non-negative reals a1,…,ana_1, \dots, a_na1​,…,an​ , how do a1a2⋯ann\sqrt[n]{a_1 a_2 \cdots a_n}na1​a2​⋯an​​ and a1+⋯+ann\frac{a_1 + \cdots + a_n}{n}na1​+⋯+an​​ compare?

   a1a2⋯ann≤a1+⋯+ann\boldsymbol{\sqrt[n]{a_1 a_2 \cdots a_n} \le \frac{a_1 + \cdots + a_n}{n}}na1​a2​⋯an​​≤na1​+⋯+an​​ Geometric mean ≤\le≤ arithmetic mean. The proof uses the equivalent form a1⋯an≤(a1+⋯+ann)na_1 \cdots a_n \le \left(\frac{a_1 + \cdots + a_n}{n}\right)^na1​⋯an​≤(na1​+⋯+an​​)n .

2. [Sums: Direct Methods] Why does a1a2≤(a1+a22)2a_1 a_2 \le \left(\frac{a_1 + a_2}{2}\right)^2a1​a2​≤(2a1​+a2​​)2 hold for all non-negative reals a1,a2a_1, a_2a1​,a2​ ?

   It is equivalent to 0≤(a1−a2)20 \le (a_1 - a_2)^20≤(a1​−a2​)2 . Multiply by 4: 4a1a2≤a12+2a1a2+a224a_1a_2 \le a_1^2 + 2a_1a_2 + a_2^24a1​a2​≤a12​+2a1​a2​+a22​ , i.e. 0≤a12−2a1a2+a220 \le a_1^2 - 2a_1a_2 + a_2^20≤a12​−2a1​a2​+a22​ . This is the case n=2n = 2n=2 of the arithmetic-geometric mean inequality.

3. [Sums: Direct Methods] PnP_nPn​ : for all non-negative reals a1,…,ana_1, \dots, a_na1​,…,an​ : a1a2⋯an≤(a1+⋯+ann)n\ a_1 a_2 \cdots a_n \le \left(\frac{a_1 + \cdots + a_n}{n}\right)^n a1​a2​⋯an​≤(na1​+⋯+an​​)n .The induction proof of the arithmetic-geometric mean inequality does not show Pn⇒Pn+1P_n \Rightarrow P_{n+1}Pn​⇒Pn+1​ . Which two implications does it show instead?

   Pn⇒Pn−1\boldsymbol{P_n \Rightarrow P_{n-1}}Pn​⇒Pn−1​ and (Pn∧P2)⇒P2n\boldsymbol{(P_n \wedge P_2) \Rightarrow P_{2n}}(Pn​∧P2​)⇒P2n​ Together with P1P_1P1​ (trivial) and P2P_2P2​ (since 0≤(a1−a2)20 \le (a_1 - a_2)^20≤(a1​−a2​)2 ).

4. [Sums: Direct Methods] PnP_nPn​ : for all non-negative reals a1,…,ana_1, \dots, a_na1​,…,an​ : a1a2⋯an≤(a1+⋯+ann)n\ a_1 a_2 \cdots a_n \le \left(\frac{a_1 + \cdots + a_n}{n}\right)^n a1​a2​⋯an​≤(na1​+⋯+an​​)n .Why do P1P_1P1​ , P2P_2P2​ , Pn⇒Pn−1\ P_n \Rightarrow P_{n-1} Pn​⇒Pn−1​ and (Pn∧P2)⇒P2n(P_n \wedge P_2) \Rightarrow P_{2n}(Pn​∧P2​)⇒P2n​ give PnP_nPn​ for every nnn ?

   Doubling gives P2jP_{2^j}P2j​ for every jjj ; from a power 2j≥n2^j \ge n2j≥n , step down to nnn .

5. [Sums: Direct Methods] PnP_nPn​ : for all non-negative reals a1,…,ana_1, \dots, a_na1​,…,an​ : a1a2⋯an≤(a1+⋯+ann)n\ a_1 a_2 \cdots a_n \le \left(\frac{a_1 + \cdots + a_n}{n}\right)^n a1​a2​⋯an​≤(na1​+⋯+an​​)n .How does the proof show Pn⇒Pn−1P_n \Rightarrow P_{n-1}Pn​⇒Pn−1​ ?

   Apply PnP_nPn​ to a1,…,an−1a_1, \dots, a_{n-1}a1​,…,an−1​ together with their mean A=1n−1∑k=1n−1akA = \frac{1}{n-1}\sum_{k=1}^{n-1} a_kA=n−11​∑k=1n−1​ak​ as the nnn -th number. The nnn numbers sum to (n−1)A+A=nA(n-1)A + A = nA(n−1)A+A=nA , so PnP_nPn​ gives (∏k=1n−1ak)A≤An\left(\prod_{k=1}^{n-1} a_k\right) A \le A^n(∏k=1n−1​ak​)A≤An . Dividing by AAA gives ∏k=1n−1ak≤An−1\prod_{k=1}^{n-1} a_k \le A^{n-1}∏k=1n−1​ak​≤An−1 , which is Pn−1P_{n-1}Pn−1​ (if A=0A = 0A=0 , all aka_kak​ are 0).

6. [Sums: Direct Methods] PnP_nPn​ : for all non-negative reals a1,…,ana_1, \dots, a_na1​,…,an​ : a1a2⋯an≤(a1+⋯+ann)n\ a_1 a_2 \cdots a_n \le \left(\frac{a_1 + \cdots + a_n}{n}\right)^n a1​a2​⋯an​≤(na1​+⋯+an​​)n .How does the proof show (Pn∧P2)⇒P2n(P_n \wedge P_2) \Rightarrow P_{2n}(Pn​∧P2​)⇒P2n​ ?

   Split a1,…,a2na_1, \dots, a_{2n}a1​,…,a2n​ into two halves of nnn ; apply PnP_nPn​ to each half, then P2P_2P2​ to the two means of the halves. With x=1n∑k=1nakx = \frac{1}{n}\sum_{k=1}^{n} a_kx=n1​∑k=1n​ak​ and y=1n∑k=n+12naky = \frac{1}{n}\sum_{k=n+1}^{2n} a_ky=n1​∑k=n+12n​ak​ : ∏k=12nak≤xnyn=(xy)n≤((x+y2)2)n\ \prod_{k=1}^{2n} a_k \le x^n y^n = (xy)^n \le \left(\left(\frac{x+y}{2}\right)^2\right)^n ∏k=12n​ak​≤xnyn=(xy)n≤((2x+y​)2)n , and x+y2=12n∑k=12nak\frac{x+y}{2} = \frac{1}{2n}\sum_{k=1}^{…

7. [Sums: Direct Methods] Index transformation: rewrite ∑k=mnak\displaystyle\sum_{k=m}^{n} a_kk=m∑n​ak​ in two ways with the index running from 000 : once forwards, once backwards.

   ∑k=0n−mam+k = ∑k=0n−man−k\displaystyle\boldsymbol{\sum_{k=0}^{n-m} a_{m+k}} \ = \ \boldsymbol{\sum_{k=0}^{n-m} a_{n-k}}k=0∑n−m​am+k​ = k=0∑n−m​an−k​ Shifting by iii also works: ∑k=mnak=∑k=m+in+iak−i=∑k=m−in−iak+i\displaystyle\sum_{k=m}^{n} a_k = \sum_{k=m+i}^{n+i} a_{k-i} = \sum_{k=m-i}^{n-i} a_{k+i}k=m∑n​ak​=k=m+i∑n+i​ak−i​=k=m−i∑n−i​ak+i​ .

8. [Sums: Direct Methods] Compute Sn=∑k=0nkaS_n = \displaystyle\sum_{k=0}^{n} kaSn​=k=0∑n​ka (for a constant aaa ) by an index transformation.

   Sn=12(n+1)na\boldsymbol{S_n = \frac{1}{2}(n+1)na}Sn​=21​(n+1)na Reverse the order: Sn=∑k=0n(n−k)aS_n = \sum_{k=0}^{n} (n-k)aSn​=∑k=0n​(n−k)a . Adding both forms, 2Sn=∑k=0nna=(n+1)na2S_n = \sum_{k=0}^{n} na = (n+1)na2Sn​=∑k=0n​na=(n+1)na .

9. [Sums: Direct Methods] Isolating terms: for Sn=∑k=0nakS_n = \displaystyle\sum_{k=0}^{n} a_kSn​=k=0∑n​ak​ , which equation do you set up and solve for SnS_nSn​ ?

   Sn+an+1=a0+∑k=0nak+1\displaystyle\boldsymbol{S_n + a_{n+1} = a_0 + \sum_{k=0}^{n} a_{k+1}}Sn​+an+1​=a0​+k=0∑n​ak+1​ , then express the right-hand sum through SnS_nSn​ . Both sides equal Sn+1S_{n+1}Sn+1​ : isolate the last term, or isolate the first term.

10. [Sums: Direct Methods] Compute the geometric sum Sn=∑k=0nakS_n = \displaystyle\sum_{k=0}^{n} a^kSn​=k=0∑n​ak ( a≠1a \ne 1a=1 ) by isolating terms.

    Sn=an+1−1a−1\boldsymbol{S_n = \frac{a^{n+1} - 1}{a - 1}}Sn​=a−1an+1−1​ Sn+an+1=Sn+1=1+∑k=0nak+1=1+aSnS_n + a^{n+1} = S_{n+1} = 1 + \sum_{k=0}^{n} a^{k+1} = 1 + aS_nSn​+an+1=Sn+1​=1+∑k=0n​ak+1=1+aSn​ .

11. [Sums: Direct Methods] Compute Sn=∑k=0nk2kS_n = \displaystyle\sum_{k=0}^{n} k 2^kSn​=k=0∑n​k2k by isolating terms.

    Sn=(n−1)2n+1+2\boldsymbol{S_n = (n-1)2^{n+1} + 2}Sn​=(n−1)2n+1+2 Sn+(n+1)2n+1=0+∑k=0n(k+1)2k+1=2∑k=0nk2k+2∑k=0n2k=2Sn+2n+2−2S_n + (n+1)2^{n+1} = 0 + \sum_{k=0}^{n} (k+1)2^{k+1} = 2\sum_{k=0}^{n} k2^k + 2\sum_{k=0}^{n} 2^k = 2S_n + 2^{n+2} - 2Sn​+(n+1)2n+1=0+∑k=0n​(k+1)2k+1=2∑k=0n​k2k+2∑k=0n​2k=2Sn​+2n+2−2 .

12. [Difference and Sum Operators] Sums can be seen as integrals over step functions. Which two notions of calculus get discrete analogues in order to compute sums?

    The derivative (the difference operator Δ\DeltaΔ ) and the antiderivative (the indefinite sum ∑\sum∑ ).

13. [Difference and Sum Operators] For a∈Za \in \mathbb{Z}a∈Z , what is the translation operator EaE^aEa ?

    Eaf(x)=f(x+a)\boldsymbol{E^a f(x) = f(x+a)}Eaf(x)=f(x+a) for all x∈Zx \in \mathbb{Z}x∈Z , for f∈RZf \in \mathbb{R}^{\mathbb{Z}}f∈RZ . So Ea:RZ→RZE^a : \mathbb{R}^{\mathbb{Z}} \to \mathbb{R}^{\mathbb{Z}}Ea:RZ→RZ , and I:=E0I := E^0I:=E0 is the identity.

14. [Difference and Sum Operators] For operators P,Q:RZ→RZP, Q : \mathbb{R}^{\mathbb{Z}} \to \mathbb{R}^{\mathbb{Z}}P,Q:RZ→RZ and a scalar α\alphaα , how are P+QP + QP+Q , αP\alpha PαP and QPQPQP defined?

    (P+Q)f=Pf+Qf\boldsymbol{(P+Q)f = Pf + Qf}(P+Q)f=Pf+Qf , (αP)f=α(Pf)\ \boldsymbol{(\alpha P)f = \alpha(Pf)} (αP)f=α(Pf) , (QP)f=Q(Pf)\ \boldsymbol{(QP)f = Q(Pf)} (QP)f=Q(Pf)

15. [Difference and Sum Operators] What is the forward difference operator Δ\DeltaΔ ?

    Δ=E1−I\boldsymbol{\Delta = E^1 - I}Δ=E1−I , so Δf(x)=f(x+1)−f(x)\boldsymbol{\Delta f(x) = f(x+1) - f(x)}Δf(x)=f(x+1)−f(x) E1f(x)=f(x+1)E^1 f(x) = f(x+1)E1f(x)=f(x+1) is translation, III the identity.

16. [Difference and Sum Operators] What is the backward difference operator ∇\nabla∇ ?

    ∇=I−E−1\boldsymbol{\nabla = I - E^{-1}}∇=I−E−1 , so ∇f(x)=f(x)−f(x−1)\boldsymbol{\nabla f(x) = f(x) - f(x-1)}∇f(x)=f(x)−f(x−1) E−1f(x)=f(x−1)E^{-1} f(x) = f(x-1)E−1f(x)=f(x−1) is translation, III the identity.

17. [Difference and Sum Operators] For n∈Nn \in \mathbb{N}n∈N : Δxn‾= ?\ \Delta x^{\underline{n}} = \; ? Δxn​=? ( xn‾=x(x−1)⋯(x−n+1)x^{\underline{n}} = x(x-1)\cdots(x-n+1)xn​=x(x−1)⋯(x−n+1) , the falling factorial; Δf(x)=f(x+1)−f(x)\Delta f(x) = f(x+1) - f(x)Δf(x)=f(x+1)−f(x) .)

    n xn−1‾\boldsymbol{n\, x^{\underline{n-1}}}nxn−1​ The analogue of ddxxn=nxn−1\frac{d}{dx} x^n = nx^{n-1}dxd​xn=nxn−1 .

18. [Difference and Sum Operators] Why is Δxn‾=(x+1)n‾−xn‾\Delta x^{\underline{n}} = (x+1)^{\underline{n}} - x^{\underline{n}}Δxn​=(x+1)n​−xn​ equal to n xn−1‾n\, x^{\underline{n-1}}nxn−1​ ? ( xn‾=x(x−1)⋯(x−n+1)x^{\underline{n}} = x(x-1)\cdots(x-n+1)xn​=x(x−1)⋯(x−n+1) .)

    Both terms share the factor x(x−1)⋯(x−n+2)=xn−1‾x(x-1)\cdots(x-n+2) = x^{\underline{n-1}}x(x−1)⋯(x−n+2)=xn−1​ : (x+1)n‾−xn‾=(x+1) xn−1‾−(x−n+1) xn−1‾=n xn−1‾(x+1)^{\underline{n}} - x^{\underline{n}} = (x+1)\,x^{\underline{n-1}} - (x-n+1)\,x^{\underline{n-1}} = n\, x^{\underline{n-1}}(x+1)n​−xn​=(x+1)xn−1​−(x−n+1)xn−1​=nxn−1​

19. [Difference and Sum Operators] For n∈Nn \in \mathbb{N}n∈N : ∇xn‾= ?\ \nabla x^{\overline{n}} = \; ? ∇xn=? ( xn‾=x(x+1)⋯(x+n−1)x^{\overline{n}} = x(x+1)\cdots(x+n-1)xn=x(x+1)⋯(x+n−1) , the rising factorial; ∇f(x)=f(x)−f(x−1)\nabla f(x) = f(x) - f(x-1)∇f(x)=f(x)−f(x−1) .)

    n xn−1‾\boldsymbol{n\, x^{\overline{n-1}}}nxn−1​ xn‾−(x−1)n‾=(x+n−1) xn−1‾−(x−1) xn−1‾x^{\overline{n}} - (x-1)^{\overline{n}} = (x+n-1)\,x^{\overline{n-1}} - (x-1)\,x^{\overline{n-1}}xn−(x−1)n=(x+n−1)xn−1​−(x−1)xn−1​ : both share the factor x(x+1)⋯(x+n−2)x(x+1)\cdots(x+n-2)x(x+1)⋯(x+n−2) .

20. [Difference and Sum Operators] For n∈N∖{0}n \in \mathbb{N} \setminus \{0\}n∈N∖{0} , how are the falling factorial x−n‾x^{\underline{-n}}x−n​ and the rising factorial x−n‾x^{\overline{-n}}x−n​ defined?

    x−n‾=1(x+1)⋯(x+n)\boldsymbol{x^{\underline{-n}} = \frac{1}{(x+1)\cdots(x+n)}}x−n​=(x+1)⋯(x+n)1​ , x−n‾=1(x−1)⋯(x−n)\quad \boldsymbol{x^{\overline{-n}} = \frac{1}{(x-1)\cdots(x-n)}}x−n​=(x−1)⋯(x−n)1​ e.g. x−1‾=1x+1x^{\underline{-1}} = \frac{1}{x+1}x−1​=x+11​ , x−2‾=1(x+1)(x+2)\ x^{\underline{-2}} = \frac{1}{(x+1)(x+2)} x−2​=(x+1)(x+2)1​ . With this, Δxn‾=n xn−1‾\Delta x^{\underline{n}} = n\, x^{\underline{n-1}}Δxn​=nxn−1​ and ∇xn‾=n xn−1‾\nabla x^{\overline{n}} = n\, x^{\overline{n-1}}∇xn=nxn−1​…

21. [Difference and Sum Operators] With x−n‾=1(x+1)⋯(x+n)x^{\underline{-n}} = \frac{1}{(x+1)\cdots(x+n)}x−n​=(x+1)⋯(x+n)1​ and Δf(x)=f(x+1)−f(x)\Delta f(x) = f(x+1) - f(x)Δf(x)=f(x+1)−f(x) : why is Δx−n‾=−n x−n−1‾\Delta x^{\underline{-n}} = -n\, x^{\underline{-n-1}}Δx−n​=−nx−n−1​ ?

    Over the common denominator (x+1)⋯(x+n+1)(x+1)\cdots(x+n+1)(x+1)⋯(x+n+1) , the numerator is (x+1)−(x+n+1)=−n(x+1) - (x+n+1) = -n(x+1)−(x+n+1)=−n . 1(x+2)⋯(x+n+1)−1(x+1)⋯(x+n)=(x+1)−(x+n+1)(x+1)⋯(x+n+1)\frac{1}{(x+2)\cdots(x+n+1)} - \frac{1}{(x+1)\cdots(x+n)} = \frac{(x+1) - (x+n+1)}{(x+1)\cdots(x+n+1)}(x+2)⋯(x+n+1)1​−(x+1)⋯(x+n)1​=(x+1)⋯(x+n+1)(x+1)−(x+n+1)​ , and 1(x+1)⋯(x+n+1)=x−n−1‾\frac{1}{(x+1)\cdots(x+n+1)} = x^{\underline{-n-1}}(x+1)⋯(x+n+1)1​=x−n−1​ .

22. [Difference and Sum Operators] With x−n‾=1(x−1)⋯(x−n)x^{\overline{-n}} = \frac{1}{(x-1)\cdots(x-n)}x−n​=(x−1)⋯(x−n)1​ and ∇f(x)=f(x)−f(x−1)\nabla f(x) = f(x) - f(x-1)∇f(x)=f(x)−f(x−1) : why is ∇x−n‾=−n x−n−1‾\nabla x^{\overline{-n}} = -n\, x^{\overline{-n-1}}∇x−n​=−nx−n−1​ ?

    Over the common denominator (x−1)⋯(x−n−1)(x-1)\cdots(x-n-1)(x−1)⋯(x−n−1) , the numerator is (x−n−1)−(x−1)=−n(x-n-1) - (x-1) = -n(x−n−1)−(x−1)=−n . 1(x−1)⋯(x−n)−1(x−2)⋯(x−n−1)=(x−n−1)−(x−1)(x−1)⋯(x−n−1)\frac{1}{(x-1)\cdots(x-n)} - \frac{1}{(x-2)\cdots(x-n-1)} = \frac{(x-n-1) - (x-1)}{(x-1)\cdots(x-n-1)}(x−1)⋯(x−n)1​−(x−2)⋯(x−n−1)1​=(x−1)⋯(x−n−1)(x−n−1)−(x−1)​ , and 1(x−1)⋯(x−n−1)=x−n−1‾\frac{1}{(x-1)\cdots(x-n-1)} = x^{\overline{-n-1}}(x−1)⋯(x−n−1)1​=x−n−1​ .

23. [Difference and Sum Operators] For f,g:Z→Rf, g : \mathbb{Z} \to \mathbb{R}f,g:Z→R , when is fff a (discrete) antiderivative or indefinite sum of ggg , written f=∑gf = \sum gf=∑g ?

    When Δf=g\boldsymbol{\Delta f = g}Δf=g , i.e. f(x+1)−f(x)=g(x)f(x+1) - f(x) = g(x)f(x+1)−f(x)=g(x) for all xxx . As in calculus, fff is only determined up to an additive constant; this is ignored, and ∑\sum∑ is treated as an operator RZ→RZ\mathbb{R}^{\mathbb{Z}} \to \mathbb{R}^{\mathbb{Z}}RZ→RZ .

24. [Difference and Sum Operators] fff is an antiderivative of ggg ( Δf=g\Delta f = gΔf=g , where Δf(x)=f(x+1)−f(x)\Delta f(x) = f(x+1) - f(x)Δf(x)=f(x+1)−f(x) ). For integers a≤ba \le ba≤b : ∑k=abg(k)= ?\ \displaystyle\sum_{k=a}^{b} g(k) = \; ? k=a∑b​g(k)=?

    f(b+1)−f(a)\boldsymbol{f(b+1) - f(a)}f(b+1)−f(a) Telescoping: ∑k=abg(k)=∑k=ab(f(k+1)−f(k))\sum_{k=a}^{b} g(k) = \sum_{k=a}^{b} \big(f(k+1) - f(k)\big)∑k=ab​g(k)=∑k=ab​(f(k+1)−f(k)) . The discrete fundamental theorem of calculus.

25. [Difference and Sum Operators] For an indefinite sum f=∑gf = \sum gf=∑g , one writes ∑acg(x):=f(x)∣ac:=f(c)−f(a)\displaystyle\sum_{a}^{c} g(x) := f(x)\Big|_a^c := f(c) - f(a)a∑c​g(x):=f(x)∣∣​ac​:=f(c)−f(a) . Which values g(k)g(k)g(k) does this add up?

    g(a)+g(a+1)+⋯+g(c−1)\boldsymbol{g(a) + g(a+1) + \cdots + g(c-1)}g(a)+g(a+1)+⋯+g(c−1) : the upper limit is excluded. So ∑ab+1g(x)=∑k=abg(k)\displaystyle\sum_{a}^{b+1} g(x) = \sum_{k=a}^{b} g(k)a∑b+1​g(x)=k=a∑b​g(k) , since ∑k=abg(k)=f(b+1)−f(a)\sum_{k=a}^{b} g(k) = f(b+1) - f(a)∑k=ab​g(k)=f(b+1)−f(a) .

26. [Difference and Sum Operators] Are Δ\DeltaΔ and the indefinite sum ∑\sum∑ linear?

    Yes: Δ(αf+βg)=αΔf+βΔg\Delta(\alpha f + \beta g) = \alpha \Delta f + \beta \Delta gΔ(αf+βg)=αΔf+βΔg and ∑(αf+βg)=α∑f+β∑g\sum(\alpha f + \beta g) = \alpha \sum f + \beta \sum g∑(αf+βg)=α∑f+β∑g .

27. [Difference and Sum Operators] For n∈Zn \in \mathbb{Z}n∈Z , n≠−1n \ne -1n=−1 : ∑xn‾= ?\ \sum x^{\underline{n}} = \; ? ∑xn​=? (indefinite sum: f=∑gf = \sum gf=∑g means f(x+1)−f(x)=g(x)f(x+1) - f(x) = g(x)f(x+1)−f(x)=g(x) )

    xn+1‾n+1\boldsymbol{\frac{x^{\underline{n+1}}}{n+1}}n+1xn+1​​ Because Δxn+1‾=(n+1) xn‾\Delta x^{\underline{n+1}} = (n+1)\, x^{\underline{n}}Δxn+1​=(n+1)xn​ . The analogue of ∫xn dx=xn+1n+1\int x^n \, dx = \frac{x^{n+1}}{n+1}∫xndx=n+1xn+1​ .

28. [Difference and Sum Operators] ∑x−1‾= ?\sum x^{\underline{-1}} = \; ?∑x−1​=? (indefinite sum: f=∑gf = \sum gf=∑g means f(x+1)−f(x)=g(x)f(x+1) - f(x) = g(x)f(x+1)−f(x)=g(x) ; x−1‾=1x+1x^{\underline{-1}} = \frac{1}{x+1}x−1​=x+11​ )

    Hx=∑i=1x1i\boldsymbol{H_x = \sum_{i=1}^{x} \frac{1}{i}}Hx​=∑i=1x​i1​ , the harmonic number Hx+1−Hx=1x+1=x−1‾H_{x+1} - H_x = \frac{1}{x+1} = x^{\underline{-1}}Hx+1​−Hx​=x+11​=x−1​ . The analogue of ∫1x dx=ln⁡x\int \frac{1}{x}\,dx = \ln x∫x1​dx=lnx .

29. [Difference and Sum Operators] How do you compute ∑k=0nk2\displaystyle\sum_{k=0}^{n} k^2k=0∑n​k2 with falling factorials ( xj‾=x(x−1)⋯(x−j+1)x^{\underline{j}} = x(x-1)\cdots(x-j+1)xj​=x(x−1)⋯(x−j+1) ), and what is the result?

    Write x2=x2‾+x1‾x^2 = x^{\underline{2}} + x^{\underline{1}}x2=x2​+x1​ and sum each term: ∑k=0nk2=n(n+12)(n+1)3\displaystyle\sum_{k=0}^{n} k^2 = \boldsymbol{\frac{n(n+\frac12)(n+1)}{3}}k=0∑n​k2=3n(n+21​)(n+1)​ ∑0n+1(x2‾+x1‾)=x3‾3∣0n+1+x2‾2∣0n+1=(n+1)n(n−1)3+(n+1)n2\displaystyle\sum_{0}^{n+1} (x^{\underline{2}} + x^{\underline{1}}) = \frac{x^{\underline{3}}}{3}\Big|_0^{n+1} + \frac{x^{\underline{2}}}{2}\Big|_0^{n+1} = \frac{(n+1)n(n-1)}{3} + \frac{(n+1)n}{2}0∑n+1​(x2​+x1​)=3x3​​∣∣​0n+1​+2x2​​∣∣​0…

30. [Difference and Sum Operators] Give a formula for ∑k=0nkm\displaystyle\sum_{k=0}^{n} k^mk=0∑n​km in terms of the Stirling numbers of the second kind Sm,jS_{m,j}Sm,j​ (partitions of an mmm -set into jjj non-empty blocks).

    ∑k=0nkm=∑j=0mSm,j(n+1)j+1‾j+1\displaystyle\sum_{k=0}^{n} k^m = \boldsymbol{\sum_{j=0}^{m} S_{m,j} \frac{(n+1)^{\underline{j+1}}}{j+1}}k=0∑n​km=j=0∑m​Sm,j​j+1(n+1)j+1​​ Expand xm=∑j=0mSm,j xj‾x^m = \sum_{j=0}^{m} S_{m,j}\, x^{\underline{j}}xm=∑j=0m​Sm,j​xj​ ( xj‾x^{\underline{j}}xj​ the falling factorial), use ∑xj‾=xj+1‾j+1\sum x^{\underline{j}} = \frac{x^{\underline{j+1}}}{j+1}∑xj​=j+1xj+1​​ and evaluate from 000 to n+1n+1n+1 ( 0j+1‾=00^{\underline{j+1}} = 00j+1​=0 ).

31. [Difference and Sum Operators] For c∈Rc \in \mathbb{R}c∈R , c≠1c \ne 1c=1 : what are Δcx\Delta c^xΔcx and ∑cx\sum c^x∑cx ? ( Δf(x)=f(x+1)−f(x)\Delta f(x) = f(x+1) - f(x)Δf(x)=f(x+1)−f(x) ; ∑\sum∑ the indefinite sum)

    Δcx=(c−1)cx\boldsymbol{\Delta c^x = (c-1)c^x}Δcx=(c−1)cx , ∑cx=cxc−1\quad \boldsymbol{\sum c^x = \frac{c^x}{c-1}}∑cx=c−1cx​ Δcx=cx+1−cx\Delta c^x = c^{x+1} - c^xΔcx=cx+1−cx .

32. [Difference and Sum Operators] Which function is the discrete analogue of exe^xex (unchanged by Δ\DeltaΔ , where Δf(x)=f(x+1)−f(x)\Delta f(x) = f(x+1) - f(x)Δf(x)=f(x+1)−f(x) )?

    2x\boldsymbol{2^x}2x Δ2x=2x+1−2x=2x\Delta 2^x = 2^{x+1} - 2^x = 2^xΔ2x=2x+1−2x=2x , and ∑2x=2x\sum 2^x = 2^x∑2x=2x .

33. [Difference and Sum Operators] For x∈Rx \in \mathbb{R}x∈R and m∈Zm \in \mathbb{Z}m∈Z : what are Δ(xm+1)\Delta \binom{x}{m+1}Δ(m+1x​) and ∑(xm)\sum \binom{x}{m}∑(mx​) ? ( Δf(x)=f(x+1)−f(x)\Delta f(x) = f(x+1) - f(x)Δf(x)=f(x+1)−f(x) ; ∑\sum∑ the indefinite sum)

    Δ(xm+1)=(xm)\boldsymbol{\Delta \binom{x}{m+1} = \binom{x}{m}}Δ(m+1x​)=(mx​) , ∑(xm)=(xm+1)\quad \boldsymbol{\sum \binom{x}{m} = \binom{x}{m+1}}∑(mx​)=(m+1x​) Pascal's rule: (x+1m+1)=(xm)+(xm+1)\binom{x+1}{m+1} = \binom{x}{m} + \binom{x}{m+1}(m+1x+1​)=(mx​)+(m+1x​) .

34. [Difference and Sum Operators] Expand Δnf(x)\Delta^n f(x)Δnf(x) in terms of values of fff . ( Δf(x)=f(x+1)−f(x)\Delta f(x) = f(x+1) - f(x)Δf(x)=f(x+1)−f(x) )

    Δnf(x)=∑k=0n(−1)n−k(nk)f(x+k)\displaystyle\Delta^n f(x) = \boldsymbol{\sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} f(x+k)}Δnf(x)=k=0∑n​(−1)n−k(kn​)f(x+k) Δn=(E−I)n=∑k=0n(−1)n−k(nk)Ek\Delta^n = (E - I)^n = \sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k} E^kΔn=(E−I)n=∑k=0n​(−1)n−k(kn​)Ek by the binomial theorem (with Ef(x)=f(x+1)E f(x) = f(x+1)Ef(x)=f(x+1) , III the identity), and Ekf(x)=f(x+k)E^k f(x) = f(x+k)Ekf(x)=f(x+k) .At x=0x = 0x=0 : Δnf(0)=∑k=0n(−1)n−k(nk)f(k)\ \Delta^n f(0) = \sum_{k=0}^{n} (-1)^{n-k}\…

35. [Difference and Sum Operators] Newton representation: a polynomial fff of degree nnn written in the falling factorials xk‾=x(x−1)⋯(x−k+1)x^{\underline{k}} = x(x-1)\cdots(x-k+1)xk​=x(x−1)⋯(x−k+1) : f(x)= ?f(x) = \; ?f(x)=? \quad ( Δf(x)=f(x+1)−f(x)\Delta f(x) = f(x+1) - f(x)Δf(x)=f(x+1)−f(x) )

    f(x)=∑k=0nΔkf(0)k! xk‾\displaystyle f(x) = \boldsymbol{\sum_{k=0}^{n} \frac{\Delta^k f(0)}{k!}\, x^{\underline{k}}}f(x)=k=0∑n​k!Δkf(0)​xk​ The analogue of the Taylor expansion f(x)=∑f(k)(0)k!xkf(x) = \sum \frac{f^{(k)}(0)}{k!} x^kf(x)=∑k!f(k)(0)​xk .

36. [Difference and Sum Operators] Newton representation: every polynomial fff of degree nnn satisfies f(x)=∑k=0nΔkf(0)k! xk‾\displaystyle f(x) = \sum_{k=0}^{n} \frac{\Delta^k f(0)}{k!}\, x^{\underline{k}}f(x)=k=0∑n​k!Δkf(0)​xk​ , where Δf(x)=f(x+1)−f(x)\Delta f(x) = f(x+1) - f(x)Δf(x)=f(x+1)−f(x) and xk‾=x(x−1)⋯(x−k+1)x^{\underline{k}} = x(x-1)\cdots(x-k+1)xk​=x(x−1)⋯(x−k+1) .How does the proof begin, and what does it then have to show?

    Write f(x)=∑i=0nbi xi‾f(x) = \sum_{i=0}^{n} b_i\, x^{\underline{i}}f(x)=∑i=0n​bi​xi​ (the xi‾x^{\underline{i}}xi​ form a basis of the polynomials) and show Δkf(0)=k! bk\Delta^k f(0) = k!\, b_kΔkf(0)=k!bk​ . Apply Δ\DeltaΔ kkk times termwise: Δkxi‾=i(i−1)⋯(i−k+1) xi−k‾=ik‾ xi−k‾\Delta^k x^{\underline{i}} = i(i-1)\cdots(i-k+1)\, x^{\underline{i-k}} = i^{\underline{k}}\, x^{\underline{i-k}}Δkxi​=i(i−1)⋯(i−k+1)xi−k​=ik​xi−k​ , so Δkf(0)=∑i=0nbi ik‾ 0i−k‾\Delta^k f(0) = \sum_{i=0}^{n} b_i\, i^{\unde…

37. [Difference and Sum Operators] Proof of the Newton representation: f(x)=∑i=0nbi xi‾f(x) = \sum_{i=0}^{n} b_i\, x^{\underline{i}}f(x)=∑i=0n​bi​xi​ gives Δkf(0)=∑i=0nbi ik‾ 0i−k‾\Delta^k f(0) = \sum_{i=0}^{n} b_i\, i^{\underline{k}}\, 0^{\underline{i-k}}Δkf(0)=∑i=0n​bi​ik​0i−k​ ( xj‾x^{\underline{j}}xj​ the falling factorial).Why does only the term i=ki = ki=k survive?

    ik‾=0\boldsymbol{i^{\underline{k}} = 0}ik​=0 for i<k\boldsymbol{i < k}i<k , and 0i−k‾=0\boldsymbol{0^{\underline{i-k}} = 0}0i−k​=0 for i>k\boldsymbol{i > k}i>k . ik‾=i(i−1)⋯(i−k+1)i^{\underline{k}} = i(i-1)\cdots(i-k+1)ik​=i(i−1)⋯(i−k+1) contains the factor 0 when 0≤i<k0 \le i < k0≤i<k , and 0j‾=0⋅(−1)⋯0^{\underline{j}} = 0 \cdot (-1) \cdots0j​=0⋅(−1)⋯ for j≥1j \ge 1j≥1 . The surviving term is bk kk‾=bk k!b_k\, k^{\underline{k}} = b_k\, k!bk​kk​=bk​k! .

38. [Difference and Sum Operators] Use the Newton representation f(x)=∑kΔkf(0)k! xk‾f(x) = \sum_{k} \frac{\Delta^k f(0)}{k!}\, x^{\underline{k}}f(x)=∑k​k!Δkf(0)​xk​ to write x3x^3x3 in falling factorials ( xk‾=x(x−1)⋯(x−k+1)x^{\underline{k}} = x(x-1)\cdots(x-k+1)xk​=x(x−1)⋯(x−k+1) ).

    x3=x1‾+3x2‾+x3‾\boldsymbol{x^3 = x^{\underline{1}} + 3x^{\underline{2}} + x^{\underline{3}}}x3=x1​+3x2​+x3​ From f(0),f(1),f(2),f(3)=0,1,8,27f(0), f(1), f(2), f(3) = 0, 1, 8, 27f(0),f(1),f(2),f(3)=0,1,8,27 : Δf(0)=1\ \Delta f(0) = 1 Δf(0)=1 , Δ2f(0)=8−2+0=6\ \Delta^2 f(0) = 8 - 2 + 0 = 6 Δ2f(0)=8−2+0=6 , Δ3f(0)=27−24+3−0=6\ \Delta^3 f(0) = 27 - 24 + 3 - 0 = 6 Δ3f(0)=27−24+3−0=6 . The coefficients 1,3,11, 3, 11,3,1 are S3,1,S3,2,S3,3S_{3,1}, S_{3,2}, S_{3,3}S3,1​,S3,2​,S3,3​ .

39. [Difference and Sum Operators] Give the explicit formula for the Stirling number of the second kind Sn,kS_{n,k}Sn,k​ (partitions of an nnn -set into kkk non-empty blocks) as an alternating sum.

    Sn,k=1k!∑i=0k(−1)k−i(ki) in\displaystyle\boldsymbol{S_{n,k} = \frac{1}{k!}\sum_{i=0}^{k} (-1)^{k-i}\binom{k}{i}\, i^n}Sn,k​=k!1​i=0∑k​(−1)k−i(ik​)in e.g. S3,2=12(0−2⋅1+8)=3S_{3,2} = \frac{1}{2}(0 - 2 \cdot 1 + 8) = 3S3,2​=21​(0−2⋅1+8)=3 .

40. [Difference and Sum Operators] Sn,k=1k!∑i=0k(−1)k−i(ki) inS_{n,k} = \frac{1}{k!}\sum_{i=0}^{k} (-1)^{k-i}\binom{k}{i}\, i^nSn,k​=k!1​∑i=0k​(−1)k−i(ik​)in , for the Stirling numbers of the second kind.How does this follow from the Newton representation f(x)=∑kΔkf(0)k! xk‾f(x) = \sum_k \frac{\Delta^k f(0)}{k!}\, x^{\underline{k}}f(x)=∑k​k!Δkf(0)​xk​ ?

    Apply it to f(x)=xnf(x) = x^nf(x)=xn : since xn=∑kSn,k xk‾x^n = \sum_k S_{n,k}\, x^{\underline{k}}xn=∑k​Sn,k​xk​ and the coefficients are unique, Sn,k=Δkf(0)k!S_{n,k} = \frac{\Delta^k f(0)}{k!}Sn,k​=k!Δkf(0)​ . Then Δkf(0)=∑i=0k(−1)k−i(ki)f(i)\Delta^k f(0) = \sum_{i=0}^{k} (-1)^{k-i}\binom{k}{i} f(i)Δkf(0)=∑i=0k​(−1)k−i(ik​)f(i) , from Δk=(E−I)k\Delta^k = (E - I)^kΔk=(E−I)k with Ef(x)=f(x+1)E f(x) = f(x+1)Ef(x)=f(x+1) .

41. [Difference and Sum Operators] Partial summation: for u,v:Z→Ru, v : \mathbb{Z} \to \mathbb{R}u,v:Z→R , ∑(uΔv)= ?\ \sum (u \Delta v) = \; ? ∑(uΔv)=? ( ∑\sum∑ the indefinite sum, Δf(x)=f(x+1)−f(x)\Delta f(x) = f(x+1) - f(x)Δf(x)=f(x+1)−f(x) , Ef(x)=f(x+1)Ef(x) = f(x+1)Ef(x)=f(x+1) .)

    uv−∑((Ev)Δu)\boldsymbol{uv - \sum ((Ev)\Delta u)}uv−∑((Ev)Δu) The analogue of integration by parts. Note the shift EvEvEv , i.e. v(x+1)v(x+1)v(x+1) .

42. [Difference and Sum Operators] Partial summation: ∑(uΔv)=uv−∑((Ev)Δu)\sum (u \Delta v) = uv - \sum ((Ev) \Delta u)∑(uΔv)=uv−∑((Ev)Δu) , where Δu(x)=u(x+1)−u(x)\Delta u(x) = u(x+1) - u(x)Δu(x)=u(x+1)−u(x) , Ev(x)=v(x+1)Ev(x) = v(x+1)Ev(x)=v(x+1) , and ∑\sum∑ is the indefinite sum ( f=∑gf = \sum gf=∑g means Δf=g\Delta f = gΔf=g ).How is partial summation proved?

    From the product rule Δ(uv)=uΔv+(Ev)Δu\Delta(uv) = u\Delta v + (Ev)\Delta uΔ(uv)=uΔv+(Ev)Δu , by applying ∑\sum∑ to both sides. u(x+1)v(x+1)−u(x)v(x)=u(x)(v(x+1)−v(x))+v(x+1)(u(x+1)−u(x))u(x+1)v(x+1) - u(x)v(x) = u(x)\big(v(x+1) - v(x)\big) + v(x+1)\big(u(x+1) - u(x)\big)u(x+1)v(x+1)−u(x)v(x)=u(x)(v(x+1)−v(x))+v(x+1)(u(x+1)−u(x)) : add and subtract u(x)v(x+1)u(x)v(x+1)u(x)v(x+1) .

43. [Difference and Sum Operators] Partial summation: ∑(uΔv)=uv−∑((Ev)Δu)\sum (u \Delta v) = uv - \sum ((Ev) \Delta u)∑(uΔv)=uv−∑((Ev)Δu) , where Δu(x)=u(x+1)−u(x)\Delta u(x) = u(x+1) - u(x)Δu(x)=u(x+1)−u(x) , Ev(x)=v(x+1)Ev(x) = v(x+1)Ev(x)=v(x+1) , and ∑\sum∑ is the indefinite sum ( f=∑gf = \sum gf=∑g means Δf=g\Delta f = gΔf=g ).Compute ∑k=0nk2k\displaystyle\sum_{k=0}^{n} k 2^kk=0∑n​k2k by partial summation: which uuu and Δv\Delta vΔv , and what is the result?

    u=x\boldsymbol{u = x}u=x , Δv=2x\boldsymbol{\Delta v = 2^x}Δv=2x ; result (n−1)2n+1+2\boldsymbol{(n-1)2^{n+1} + 2}(n−1)2n+1+2 Δu=1\Delta u = 1Δu=1 , v=2xv = 2^xv=2x , Ev=2x+1Ev = 2^{x+1}Ev=2x+1 : ∑0n+1x2x=x2x∣0n+1−∑0n+12x+1=x2x∣0n+1−2⋅2x∣0n+1=(n+1)2n+1−2⋅2n+1+2\ \displaystyle\sum_{0}^{n+1} x2^x = x2^x\Big|_0^{n+1} - \sum_{0}^{n+1} 2^{x+1} = x2^x\Big|_0^{n+1} - 2 \cdot 2^x\Big|_0^{n+1} = (n+1)2^{n+1} - 2 \cdot 2^{n+1} + 2 0∑n+1​x2x=x2x∣∣​0n+1​−0∑n+1​2x+1=x2x∣∣​0n+1​−2⋅2x∣∣​0n+1​=(n+1)2n+1−2⋅2n+1…

44. [Difference and Sum Operators] ∑k=1nHk= ?\displaystyle\sum_{k=1}^{n} H_k = \; ?k=1∑n​Hk​=? \quad ( Hk=∑i=1k1iH_k = \sum_{i=1}^{k} \frac{1}{i}Hk​=∑i=1k​i1​ , the harmonic number)

    (n+1)(Hn+1−1)\boldsymbol{(n+1)(H_{n+1} - 1)}(n+1)(Hn+1​−1) By partial summation with u=Hxu = H_xu=Hx​ and Δv=1\Delta v = 1Δv=1 . Check: n=2n = 2n=2 gives 1+32=52=3(116−1)1 + \frac32 = \frac52 = 3\left(\frac{11}{6} - 1\right)1+23​=25​=3(611​−1) .

45. [Difference and Sum Operators] Partial summation: ∑(uΔv)=uv−∑((Ev)Δu)\sum (u \Delta v) = uv - \sum ((Ev) \Delta u)∑(uΔv)=uv−∑((Ev)Δu) , where Δu(x)=u(x+1)−u(x)\Delta u(x) = u(x+1) - u(x)Δu(x)=u(x+1)−u(x) , Ev(x)=v(x+1)Ev(x) = v(x+1)Ev(x)=v(x+1) , and ∑\sum∑ is the indefinite sum ( f=∑gf = \sum gf=∑g means Δf=g\Delta f = gΔf=g ).To compute ∑k=1nHk\displaystyle\sum_{k=1}^{n} H_kk=1∑n​Hk​ ( HkH_kHk​ the harmonic number), why choose u=Hxu = H_xu=Hx​ and Δv=1\Delta v = 1Δv=1 ?

    Then Δu=1x+1\Delta u = \frac{1}{x+1}Δu=x+11​ and Ev=x+1Ev = x+1Ev=x+1 , so the remaining sum is ∑1\sum 1∑1 . ∑1n+1Hx=Hx x∣1n+1−∑1n+1(x+1)1x+1=Hn+1(n+1)−1−x∣1n+1=(n+1)(Hn+1−1)\displaystyle\sum_{1}^{n+1} H_x = H_x\, x\Big|_1^{n+1} - \sum_{1}^{n+1} (x+1)\frac{1}{x+1} = H_{n+1}(n+1) - 1 - x\Big|_1^{n+1} = (n+1)(H_{n+1} - 1)1∑n+1​Hx​=Hx​x∣∣​1n+1​−1∑n+1​(x+1)x+11​=Hn+1​(n+1)−1−x∣∣​1n+1​=(n+1)(Hn+1​−1) Here ∑ab+1g(x):=f(b+1)−f(a)\displaystyle\sum_{a}^{b+1} g(x) := f(b+1) - f(a)a∑b+1​g(x):=f(b+1)−f(a)…

46. [Difference and Sum Operators] ∑k=1n(km)Hk= ?\displaystyle\sum_{k=1}^{n} \binom{k}{m} H_k = \; ?k=1∑n​(mk​)Hk​=? \quad ( m≥1m \ge 1m≥1 , Hk=∑i=1k1iH_k = \sum_{i=1}^{k} \frac{1}{i}Hk​=∑i=1k​i1​ the harmonic number)

    (n+1m+1)(Hn+1−1m+1)\boldsymbol{\binom{n+1}{m+1}\left(H_{n+1} - \frac{1}{m+1}\right)}(m+1n+1​)(Hn+1​−m+11​) By partial summation with u=Hxu = H_xu=Hx​ and Δv=(xm)\Delta v = \binom{x}{m}Δv=(mx​) , so Δu=1x+1\Delta u = \frac{1}{x+1}Δu=x+11​ and v=(xm+1)v = \binom{x}{m+1}v=(m+1x​) .

47. [Difference and Sum Operators] Partial summation: ∑(uΔv)=uv−∑((Ev)Δu)\sum (u \Delta v) = uv - \sum ((Ev) \Delta u)∑(uΔv)=uv−∑((Ev)Δu) , where Δu(x)=u(x+1)−u(x)\Delta u(x) = u(x+1) - u(x)Δu(x)=u(x+1)−u(x) , Ev(x)=v(x+1)Ev(x) = v(x+1)Ev(x)=v(x+1) , and ∑\sum∑ is the indefinite sum ( f=∑gf = \sum gf=∑g means Δf=g\Delta f = gΔf=g ).For ∑(xm)Hx\sum \binom{x}{m} H_x∑(mx​)Hx​ with u=Hxu = H_xu=Hx​ , Δv=(xm)\Delta v = \binom{x}{m}Δv=(mx​) , the remaining sum is ∑(x+1m+1)1x+1\sum \binom{x+1}{m+1}\frac{1…

    (x+1m+1)1x+1=1m+1(xm)\boldsymbol{\binom{x+1}{m+1}\frac{1}{x+1} = \frac{1}{m+1}\binom{x}{m}}(m+1x+1​)x+11​=m+11​(mx​) , whose indefinite sum is 1m+1(xm+1)\frac{1}{m+1}\binom{x}{m+1}m+11​(m+1x​) . So ∑k=1n(km)Hk=Hx(xm+1)∣1n+1−1m+1(xm+1)∣1n+1\displaystyle\sum_{k=1}^{n} \binom{k}{m} H_k = H_x\binom{x}{m+1}\Big|_1^{n+1} - \frac{1}{m+1}\binom{x}{m+1}\Big|_1^{n+1}k=1∑n​(mk​)Hk​=Hx​(m+1x​)∣∣​1n+1​−m+11​(m+1x​)∣∣​1n+1​ , and (1m+1)=0\binom{1}{m+1} = 0(m+11​)=0 for m≥1m \ge 1m≥1 .

48. [Difference and Sum Operators] The identity ∑(uΔv)=uv−∑((Ev)Δu)\sum (u \Delta v) = uv - \sum ((Ev)\Delta u)∑(uΔv)=uv−∑((Ev)Δu) , the discrete analogue of integration by parts, is called partial summation.

49. [Inversions] What is a basis sequence?

    A sequence of polynomials p0(x),p1(x),…p_0(x), p_1(x), \dotsp0​(x),p1​(x),… where pip_ipi​ has degree iii . e.g. (xn)n∈N(x^n)_{n \in \mathbb{N}}(xn)n∈N​ , (xn‾)n∈N\ (x^{\underline{n}})_{n \in \mathbb{N}} (xn​)n∈N​ (falling factorials), ((x−1)n)n∈N\ ((x-1)^n)_{n \in \mathbb{N}} ((x−1)n)n∈N​ .

50. [Inversions] p0(x),p1(x),…p_0(x), p_1(x), \dotsp0​(x),p1​(x),… is a basis sequence ( pip_ipi​ of degree iii ) and p(x)p(x)p(x) is a polynomial of degree nnn . What can you say about writing ppp in terms of the pkp_kpk​ ?

    There are unique numbers a0,…,ana_0, \dots, a_na0​,…,an​ with p(x)=∑k=0nak pk(x)p(x) = \sum_{k=0}^{n} a_k\, p_k(x)p(x)=∑k=0n​ak​pk​(x) . p0,…,pnp_0, \dots, p_np0​,…,pn​ have degrees 0,…,n0, \dots, n0,…,n , so they form a basis of the polynomials of degree at most nnn .

51. [Inversions] (pn)(p_n)(pn​) and (qn)(q_n)(qn​) are two basis sequences ( pn,qnp_n, q_npn​,qn​ polynomials of degree nnn ). What are their connection coefficients an,ka_{n,k}an,k​ and bn,kb_{n,k}bn,k​ ?

    The unique numbers with qn=∑k=0nan,k pk\boldsymbol{q_n = \sum_{k=0}^{n} a_{n,k}\, p_k}qn​=∑k=0n​an,k​pk​ and pn=∑k=0nbn,k qk\boldsymbol{p_n = \sum_{k=0}^{n} b_{n,k}\, q_k}pn​=∑k=0n​bn,k​qk​ . For k>nk > nk>n , an,k=bn,k=0a_{n,k} = b_{n,k} = 0an,k​=bn,k​=0 .

52. [Inversions] (pn)n∈N(p_n)_{n \in \mathbb{N}}(pn​)n∈N​ and (qn)n∈N(q_n)_{n \in \mathbb{N}}(qn​)n∈N​ are basis sequences ( pn,qnp_n, q_npn​,qn​ polynomials of degree nnn ), with connection coefficients an,k,bn,ka_{n,k}, b_{n,k}an,k​,bn,k​ : qn=∑k=0nan,k pk\ q_n = \sum_{k=0}^{n} a_{n,k}\, p_k qn​=∑k=0n​an,k​pk​ and pn=∑k=0nbn,k qkp_n = \sum_{k=0}^{n} b_{n,k}\, q_kpn​=∑k=0n​bn,k​qk​ (and an,k=bn,k=0a_{n,k} = b_{n,k} = 0an,k​=bn,k​=0 for k>nk > nk>n ).What is ∑kan,k bk,m\displaystyle\sum_{k} a_{n,k}…

    1 if n=mn = mn=m , and 0 if n≠mn \ne mn=m . So the lower triangular matrices An=(ai,j)0≤i,j≤nA_n = (a_{i,j})_{0 \le i,j \le n}An​=(ai,j​)0≤i,j≤n​ and Bn=(bi,j)0≤i,j≤nB_n = (b_{i,j})_{0 \le i,j \le n}Bn​=(bi,j​)0≤i,j≤n​ satisfy AnBn=IA_n B_n = IAn​Bn​=I .

53. [Inversions] (pn)n∈N(p_n)_{n \in \mathbb{N}}(pn​)n∈N​ and (qn)n∈N(q_n)_{n \in \mathbb{N}}(qn​)n∈N​ are basis sequences ( pn,qnp_n, q_npn​,qn​ polynomials of degree nnn ), with connection coefficients an,k,bn,ka_{n,k}, b_{n,k}an,k​,bn,k​ : qn=∑k=0nan,k pk\ q_n = \sum_{k=0}^{n} a_{n,k}\, p_k qn​=∑k=0n​an,k​pk​ and pn=∑k=0nbn,k qkp_n = \sum_{k=0}^{n} b_{n,k}\, q_kpn​=∑k=0n​bn,k​qk​ (and an,k=bn,k=0a_{n,k} = b_{n,k} = 0an,k​=bn,k​=0 for k>nk > nk>n ).Why is ∑kan,k bk,m\sum_{k} a_{n,k}\, b_{k,m}∑k​a…

    Substitute pk=∑mbk,mqmp_k = \sum_m b_{k,m} q_mpk​=∑m​bk,m​qm​ into qn=∑kan,kpkq_n = \sum_k a_{n,k} p_kqn​=∑k​an,k​pk​ and compare coefficients (they are unique). qn=∑k=0nan,k∑m=0kbk,m qm=∑m=0nqm∑k=mnan,k bk,mq_n = \sum_{k=0}^{n} a_{n,k} \sum_{m=0}^{k} b_{k,m}\, q_m = \sum_{m=0}^{n} q_m \sum_{k=m}^{n} a_{n,k}\, b_{k,m}qn​=∑k=0n​an,k​∑m=0k​bk,m​qm​=∑m=0n​qm​∑k=mn​an,k​bk,m​ , so the coefficient of qmq_mqm​ must be 1 for m=nm = nm=n and 0 otherwise.

54. [Inversions] (pn)n∈N(p_n)_{n \in \mathbb{N}}(pn​)n∈N​ and (qn)n∈N(q_n)_{n \in \mathbb{N}}(qn​)n∈N​ are basis sequences ( pn,qnp_n, q_npn​,qn​ polynomials of degree nnn ), with connection coefficients an,k,bn,ka_{n,k}, b_{n,k}an,k​,bn,k​ : qn=∑k=0nan,k pk\ q_n = \sum_{k=0}^{n} a_{n,k}\, p_k qn​=∑k=0n​an,k​pk​ and pn=∑k=0nbn,k qkp_n = \sum_{k=0}^{n} b_{n,k}\, q_kpn​=∑k=0n​bn,k​qk​ (and an,k=bn,k=0a_{n,k} = b_{n,k} = 0an,k​=bn,k​=0 for k>nk > nk>n ).Inversion theorem: for sequences (un)n∈N(u_n)_{n…

    ∀n: un=∑k=0nbn,k vk\boldsymbol{\forall n:\ u_n = \sum_{k=0}^{n} b_{n,k}\, v_k}∀n: un​=∑k=0n​bn,k​vk​

55. [Inversions] (pn)n∈N(p_n)_{n \in \mathbb{N}}(pn​)n∈N​ and (qn)n∈N(q_n)_{n \in \mathbb{N}}(qn​)n∈N​ are basis sequences ( pn,qnp_n, q_npn​,qn​ polynomials of degree nnn ), with connection coefficients an,k,bn,ka_{n,k}, b_{n,k}an,k​,bn,k​ : qn=∑k=0nan,k pk\ q_n = \sum_{k=0}^{n} a_{n,k}\, p_k qn​=∑k=0n​an,k​pk​ and pn=∑k=0nbn,k qkp_n = \sum_{k=0}^{n} b_{n,k}\, q_kpn​=∑k=0n​bn,k​qk​ (and an,k=bn,k=0a_{n,k} = b_{n,k} = 0an,k​=bn,k​=0 for k>nk > nk>n ).Why is ∀n: vn=∑k=0nan,kuk \ \forall n:\ v_n = \s…

    The matrices An=(ai,j)A_n = (a_{i,j})An​=(ai,j​) and Bn=(bi,j)B_n = (b_{i,j})Bn​=(bi,j​) are inverse to each other, so v=Anu ⟺ u=Bnvv = A_n u \iff u = B_n vv=An​u⟺u=Bn​v . Here u=(u0,…,un)u = (u_0, \dots, u_n)u=(u0​,…,un​) , v=(v0,…,vn)v = (v_0, \dots, v_n)v=(v0​,…,vn​) , and AnBn=IA_n B_n = IAn​Bn​=I because ∑kan,kbk,m\sum_k a_{n,k} b_{k,m}∑k​an,k​bk,m​ is 1 for n=mn = mn=m and 0 otherwise.

56. [Inversions] Which numbers are the connection coefficients between the basis sequences (xn)(x^n)(xn) and (xn‾)(x^{\underline{n}})(xn​) (falling factorials)?

    The Stirling numbers: xn=∑k=0nSn,k xk‾\boldsymbol{x^n = \sum_{k=0}^{n} S_{n,k}\, x^{\underline{k}}}xn=∑k=0n​Sn,k​xk​ and xn‾=∑k=0n(−1)n−ksn,k xk\boldsymbol{x^{\underline{n}} = \sum_{k=0}^{n} (-1)^{n-k} s_{n,k}\, x^k}xn​=∑k=0n​(−1)n−ksn,k​xk . Sn,kS_{n,k}Sn,k​ : partitions of an nnn -set into kkk non-empty blocks (second kind). sn,ks_{n,k}sn,k​ : nnn -permutations with kkk cycles (first kind).

57. [Inversions] Simplify ∑k≥0Sn,k (−1)k−m sk,m\displaystyle\sum_{k \ge 0} S_{n,k}\, (-1)^{k-m}\, s_{k,m}k≥0∑​Sn,k​(−1)k−msk,m​ , where Sn,kS_{n,k}Sn,k​ and sk,ms_{k,m}sk,m​ are the Stirling numbers of the second and first kind.

    1 if n=mn = mn=m , and 0 if n≠mn \ne mn=m . Sn,kS_{n,k}Sn,k​ and (−1)n−ksn,k(-1)^{n-k}s_{n,k}(−1)n−ksn,k​ are the connection coefficients of (xn‾)(x^{\underline{n}})(xn​) and (xn)(x^n)(xn) : xn=∑kSn,k xk‾x^n = \sum_k S_{n,k}\, x^{\underline{k}}xn=∑k​Sn,k​xk​ and xn‾=∑k(−1)n−ksn,k xkx^{\underline{n}} = \sum_k (-1)^{n-k}s_{n,k}\, x^kxn​=∑k​(−1)n−ksn,k​xk .

58. [Inversions] Stirling inversion: for sequences (un)(u_n)(un​) , (vn)(v_n)(vn​) , ∀n: vn=∑k=0nSn,k uk \ \forall n:\ v_n = \sum_{k=0}^{n} S_{n,k}\, u_k \; ∀n: vn​=∑k=0n​Sn,k​uk​ is equivalent to … ? ( Sn,kS_{n,k}Sn,k​ , sn,ks_{n,k}sn,k​ : Stirling numbers of the second and first kind.)

    ∀n: un=∑k=0n(−1)n−ksn,k vk\boldsymbol{\forall n:\ u_n = \sum_{k=0}^{n} (-1)^{n-k} s_{n,k}\, v_k}∀n: un​=∑k=0n​(−1)n−ksn,k​vk​ Because xn=∑kSn,k xk‾x^n = \sum_k S_{n,k}\, x^{\underline{k}}xn=∑k​Sn,k​xk​ and xn‾=∑k(−1)n−ksn,k xkx^{\underline{n}} = \sum_k (-1)^{n-k}s_{n,k}\, x^kxn​=∑k​(−1)n−ksn,k​xk (connection coefficients of two basis sequences).

59. [Inversions] Which numbers are the connection coefficients between the basis sequences ((x−1)n)((x-1)^n)((x−1)n) and (xn)(x^n)(xn) , and why?

    xn=∑k=0n(nk)(x−1)k\boldsymbol{x^n = \sum_{k=0}^{n} \binom{n}{k}(x-1)^k}xn=∑k=0n​(kn​)(x−1)k and (x−1)n=∑k=0n(−1)n−k(nk)xk\boldsymbol{(x-1)^n = \sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k} x^k}(x−1)n=∑k=0n​(−1)n−k(kn​)xk Binomial theorem, applied to xn=((x−1)+1)nx^n = ((x-1) + 1)^nxn=((x−1)+1)n and to (x+(−1))n(x + (-1))^n(x+(−1))n .

60. [Inversions] Simplify ∑k≥0(nk)(−1)k−m(km)\displaystyle\sum_{k \ge 0} \binom{n}{k} (-1)^{k-m} \binom{k}{m}k≥0∑​(kn​)(−1)k−m(mk​) .

    1 if n=mn = mn=m , and 0 if n≠mn \ne mn=m . (nk)\binom{n}{k}(kn​) and (−1)n−k(nk)(-1)^{n-k}\binom{n}{k}(−1)n−k(kn​) are the connection coefficients of ((x−1)n)((x-1)^n)((x−1)n) and (xn)(x^n)(xn) .

61. [Inversions] Binomial inversion: for sequences (un)(u_n)(un​) , (vn)(v_n)(vn​) , ∀n: vn=∑k=0n(nk)uk \ \forall n:\ v_n = \sum_{k=0}^{n} \binom{n}{k} u_k \; ∀n: vn​=∑k=0n​(kn​)uk​ is equivalent to … ?

    ∀n: un=∑k=0n(−1)n−k(nk)vk\boldsymbol{\forall n:\ u_n = \sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k} v_k}∀n: un​=∑k=0n​(−1)n−k(kn​)vk​ Because xn=∑k(nk)(x−1)kx^n = \sum_k \binom{n}{k}(x-1)^kxn=∑k​(kn​)(x−1)k and (x−1)n=∑k(−1)n−k(nk)xk(x-1)^n = \sum_k (-1)^{n-k}\binom{n}{k}x^k(x−1)n=∑k​(−1)n−k(kn​)xk (connection coefficients of two basis sequences).

62. [Inversions] What is the symmetric version of binomial inversion, and how is it obtained?

    ∀n: vn=∑k=0n(−1)k(nk)uk ⟺ ∀n: un=∑k=0n(−1)k(nk)vk\boldsymbol{\forall n:\ v_n = \sum_{k=0}^{n} (-1)^k\binom{n}{k} u_k \iff \forall n:\ u_n = \sum_{k=0}^{n} (-1)^k\binom{n}{k} v_k}∀n: vn​=∑k=0n​(−1)k(kn​)uk​⟺∀n: un​=∑k=0n​(−1)k(kn​)vk​ Replace unu_nun​ by (−1)nun(-1)^n u_n(−1)nun​ in (∀n: vn=∑k(nk)uk) ⟺ (∀n: un=∑k(−1)n−k(nk)vk)\big(\forall n:\ v_n = \sum_k \binom{n}{k} u_k\big) \iff \big(\forall n:\ u_n = \sum_k (-1)^{n-k}\binom{n}{k} v_k\big)(∀n: vn​=∑k​(kn​)uk​)⟺(∀n: un​=∑k​(−1)n−k(kn​)vk​) .

63. [Inversions] DkD_kDk​ is the number of derangements (fixed-point-free permutations) of a kkk -set. Why is n!=∑k=0n(nk)Dk\displaystyle n! = \sum_{k=0}^{n} \binom{n}{k} D_kn!=k=0∑n​(kn​)Dk​ ?

    (nk)Dk\boldsymbol{\binom{n}{k} D_k}(kn​)Dk​ counts the nnn -permutations with exactly n−kn - kn−k fixed points. Choose the n−kn - kn−k fixed points ( (nn−k)=(nk)\binom{n}{n-k} = \binom{n}{k}(n−kn​)=(kn​) ways), then derange the other kkk elements.

64. [Inversions] n!=∑k=0n(nk)Dkn! = \sum_{k=0}^{n} \binom{n}{k} D_kn!=∑k=0n​(kn​)Dk​ , where DkD_kDk​ is the number of derangements (fixed-point-free permutations) of a kkk -set.How does binomial inversion give a formula for DnD_nDn​ , and what is it?

    Invert with vn=n!v_n = n!vn​=n! and uk=Dku_k = D_kuk​=Dk​ : Dn=n!∑k=0n(−1)kk!\displaystyle\boldsymbol{D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}}Dn​=n!k=0∑n​k!(−1)k​ Binomial inversion: vn=∑k(nk)ukv_n = \sum_k \binom{n}{k}u_kvn​=∑k​(kn​)uk​ for all nnn ⟺ \iff⟺ un=∑k(−1)n−k(nk)vku_n = \sum_k (-1)^{n-k}\binom{n}{k}v_kun​=∑k​(−1)n−k(kn​)vk​ for all nnn . Dn=∑k=0n(−1)n−k(nk)k!=n!∑k=0n(−1)n−k(n−k)!D_n = \sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k} k! = n!\sum_{k=0}^{n} \frac{(-1)^{n-k}}{(n-k)!}Dn​=∑k=0n​(−1)…