TAOCP 1.2.5 Exercise 7

We have the generalized termial function defined for all real numbers $x$ by $x? = \sum_{k=1}^x k = 1 + 2 + \cdots + x.$ For integer $x$, this is exactly the usual arithmetic series formula, and for n...

taocpmathematicsalgorithmsvolume-1

Section 1.2.5: Permutations and Factorials

Exercise 7. [**] [M10] Show that the "generalized termial" function in Eq. (10) satisfies the identity $x? = x + (x-1)?$ for all real numbers $x$.

Verified: yes
Solve time: 45s

We have the generalized termial function defined for all real numbers $x$ by

$x? = \sum_{k=1}^x k = 1 + 2 + \cdots + x.$

For integer $x$, this is exactly the usual arithmetic series formula, and for non-integer $x$ it is extended using the formula

$x? = \frac{1}{2} x (x+1).$

We verify the identity $x? = x + (x-1)?$ directly: substituting the formula,

$(x-1)? = \frac{1}{2} (x-1)x,$

so

$x + (x-1)? = x + \frac{1}{2}(x-1)x = \frac{2x + x^2 - x}{2} = \frac{x^2 + x}{2} = x?.$

This completes the proof.

∎