The sum of the k-th powers of the first n positive integers – easy algorithm

Revision en1, by SirRembocodina, 2023-02-28 05:55:08

Suppose you want to know this sum for some n and k:

Here are the well known formulas for the first several k:

But suppose you forgot them. What to do? Luckily, there is an easy algorithm to generate those formulas.

First of all, let's prove a theorem.

### Theorem

Suppose for every integer non-negative n:

where f and g are polynoms. Then for some constant c:

### Proof

For every positive integer n:

These two polynoms are equal in an infinite number of points, which means that they are identical. Which allows us to say:

### Application

Let's say we want to find the formula for the sum of squares. Then using our theorem we can create such an algorithm:

Now let's run the same algorithm to find the formula for the sum of cubes:

#### History

Revisions

Rev. Lang. By When Δ Comment
ru5 SirRembocodina 2023-02-28 05:59:12 1290
en1 SirRembocodina 2023-02-28 05:55:08 1446 Initial revision for English translation
ru4 SirRembocodina 2023-02-28 05:54:39 0 (опубликовано)
ru3 SirRembocodina 2023-02-28 05:47:24 20 Мелкая правка: 'noms. Then:\n\n![ ](' -> 'noms. Then for some constant c:\n\n![ ]('
ru2 SirRembocodina 2023-02-28 05:45:38 833
ru1 SirRembocodina 2023-02-28 05:34:18 859 Первая редакция (сохранено в черновиках)