Som oneven delers

a) Noem $S(n) = f(n+1) + f(n+2) + ... + f(2n)$. Nu is $S(n)=n^2$. Dit kunnen we bewijzen met inductie:

• $S(1) = f(2) = 1 = 1^2$.
• $S(n+1) = S(n) - f(n+1) + f(2n+1) + f(2n+2)$. En doordat de grootste oneven deler van $2\cdot(n+1)$ gelijk is aan die van $n+1$, is $f(2n+2) = f(n+1)$. Daaruit volgt dat $S(n+1) = S(n) - f(n+1) + f(n+1) + f(2n+1) = S(n) + f(2n+1)$. En aangezien $2n+1$ oneven is, is $f(2n+1)=2n+1$, dus $S(n+1) = S(n) + 2n+1 = n^2 + 2n + 1 = (n+1)^2$.

b)
Gebruikmakend van deel a) vinden we dat
$$f(1) + f(2) + f(3)+ ... + f(2^n)=1+ \sum_{k=0}^{n-1} S(2^k) =1+\sum_{k=0}^{n-1} 4^k = \frac{4^n+2}{3}.$$