The sums are finite since
n
k
= 0 when k > n. Both of these identities have elementary
combinatorial proofs. But when r ≥ 3, the sum
k≥0
n
rk
is rarely mentioned
because its closed form is more complex. (See Gould [1]. A special case appears in [3]
as problem 1.42(f).)