The function \(f(n)\) is defined for positive integers \(n\) according to the rules \[f(1)=1,\qquad f(2n)=f(n),\qquad f(2n+1)=(f(n))^2-2.\] The value of \(f(1)+f(2)+f(3)+\cdots+f(100)\) is
\(-86\),
\(-31\),
\(23\),
\(58\).
Initially, this function looks complicated. We’ll try to get a feel for what’s happening by working out the first few values.
Using the given rules, we calculate the first few values to be \(f(2)=1\), \(f(3)=-1\), \(f(4)=1\), \(f(5)=-1\) and \(f(6)=-1\).
We might guess that \(f(n)\) can only take values \(1\) and \(-1\).
We’ve shown we start with a sequence of \(1\)s and \(-1\)s; what happens if we calculate the next few numbers?
If we use the first rule, \(f(2n)=f(n)\), then the new term has the same value as \(f(n)\), which would be \(1\) or \(-1\).
If we use the second rule, \(f(2n+1)=(f(n))^2-2\), then we always have a \(-1\) regardless of whether or not \(f(n)\) is \(1\) or \(-1\), as \(1^2-2=-1\) and \((-1)^2-2=-1\).
This argument can then be repeated, showing that any new terms must take values \(1\) or \(-1\), and so our observation was correct.
These calculations also show that the only way for \(f(n)\) to be \(1\) (rather than \(-1\)) is if the second rule is never needed to calculate it.
The only terms in the sequence that we can evaluate using only the first rule are the \(1\)st, \(2\)nd, \(4\)th, \(8\)th, \(16\)th, \(32\)nd and \(64\)th (i.e. the powers of \(2\)).
Hence \(f(n)=1\) if \(n\) is a power of \(2\) and \(f(n)=-1\) otherwise.
As there are \(7\) powers of \(2\) between \(1\) and \(100\), we get that
\[f(1)+f(2)+f(3)+\cdots+f(100)=7\times1+93\times(-1)=-86,\]
and so the correct answer is (a).
The key idea we used here is known as strong induction.
This is a form of “proof by induction” where we show that, if a claim holds for ALL values smaller than \(n\), then it also holds for \(n\).
