Review question

# Two rules generate a sequence; what do the first 100 terms add to? Add to your resource collection Remove from your resource collection Add notes to this resource View your notes for this resource

Ref: R7943

## Solution

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

1. $-86$,

2. $-31$,

3. $23$,

4. $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$.