MathDB

A mathematical frog jumps along the number line. The frog starts at

1

, and jumps according to the following rule: if the frog is at integer

n

, then it can jump either to

n+1

or to

n + 2^{m_n+1}

where

2^{m_n}

is the largest power of

2

that is a factor of

n.

Show that if

k \geq 2

is a positive integer and

i

is a nonnegative integer, then the minimum number of jumps needed to reach

2^ik

is greater than the minimum number of jumps needed to reach

2^i.

5