MathCastle
PutnamSuperchallengeIntegrals I: Feynman's Trick

Integrals I: Feynman's Trick · Superchallenge problem

Define f(1)=1f(1) = 1 and f(n)=f(⌊n/2⌋)+1f(n) = f(\lfloor n/2\rfloor) + 1 for n≥2n \ge 2. Strong induction proves f(n)=⌊log⁡2n⌋+1f(n) = \lfloor\log_2 n\rfloor + 1. Compute ∑n=1100f(n)\displaystyle\sum_{n=1}^{100} f(n).