Dagens kort – Induksjon og rekursjon

Steget bruker kun ett tidligere ledd ($H_{n-1}$), så svak induksjon er nok: $H_{k+1}=2H_k+1\overset{IH}{=}2(2^k-1)+1=2^{k+1}-1$. Sterk induksjon kreves først når steget refererer til flere/vilkårlige tidligere ledd.