Svaret er s(n) = 2^n-1. Dette er ikke så vanskelig å gjette hvis man observerer at s(1)=1, s(2)=2, s(3)=4 og s(4)=8, men hvordan beviser man at det holder for alle naturlige tall n? Her er én måte å tenke på. Alle summene som gir n må ha et første ledd. Noen har første ledd lik 1, andre har første ledd lik 2 osv. Hvor mange er det av hver type? Vel, hvis første ledd er 1, må de andre leddene summere seg opp til n-1, og det er s(n-1) slike kombinasjoner. Dersom første ledd er 2, må de andre leddene summeres til n-2, og det kan gjøres på s(n-2) måter. Slik kan vi fortsette. I alt finnes det derfor

s(n-1) + s(n-2) + s(n-3) + ... + s(1) + 1

måter å skrive n som en sum på (det siste leddet er for å få med den summen som bare består av n selv). Vi har altså

s(n) = s(n-1) + s(n-2) + s(n-3) + ... + s(1) + 1

Hvis påstanden er sann for alle k mindre enn n, er derfor

s(n) = 2^n.-2 + 2^n-3 + 2^n-4 + ... + 1 + 1

Alle ledd unntatt det siste utgjør en endelig geometrisk rekke med sum 2^n-1 - 1. Legger vi til det siste leddet, får vi s(n) = 2^n-1 som vi skulle vise.

Vi har dermed vist at dersom formelen s(k)=2^k-1 holder for alle k < n, gjelder den også for n. Det følger (induksjon) at formelen gjelder for alle naturlige tall.