# Easy proof of a recursive function

I have a question about an inductive proof all of you will find easy but I have a couple of questions. Don't be too annoyed!

A function $f$ is defined on the positive integers by $f(1) = 1$ and for $n > 1$, if $n$ is even then $f(n) = 2f(\frac n2)$ and if $n$ is odd then $f(n) = f(n-1)$. Prove by induction that $f(n) ≤ n$ for all $n ≥ 1$.

$f(1) = 1$
$f(2) = 2 * f(2/2) = 2 * f(1) = 2 * 1 = 2$
$f(3) = f(3-1) = f(2) = 2$
$f(4) = 2 * f(4/2) = 2 * f(2) = 4$
$f(5) = f(4) = 4$

and so on.

I assumed that, since the function is defined by two parts (for even and odd numbers), I will need two inductive proofs, one for even numbers and one for odd numbers.

Odd numbers:

Basis: $f(1) = 1$

Inductive hypothesis:

We assume that $f(n) ≤ n$ holds.

Induction step:

It is to be shown that $f(n+2) ≤ n+2$, for all odd $n ≥ 1$.

So far so good, now come my mistakes, I guess.

$f(n+2) = f(n) + f(2)$. (Is this step justified? I somehow doubt it.)

$f(n) + f(2) ≤ n + f(2)$ by inductive hypothesis

$n + f(2) = n + 2$

That concludes it for odd numbers.

Even numbers:

Basis : $f(2) = 2$

Inductive hypothesis:

We assume that $f(n) ≤ n$ holds.

Induction step:

It is to be shown that $f(n+2) ≤ n+2$, for all even $n ≥ 1$.

$f(n+2) = f(n) + f(2)$

$f(n) + f(2) ≤ n + f(2)$ by inductive hypothesis

$n + f(2) = n + 2$

q.e.d

But that cannot be true. It is far too easy and I expected some manipulations of the formulae.

Furthermore, after completing this proof (?) I now have my doubts that the distinction between even and odd numbers is necessary in the inductive proof. It would then look more like this:

Basis: $f(1) = 1$

Inductive hypothesis:

We assume that $f(n) ≤ n$ holds.

Induction step:

It is to be shown that $f(n+1) ≤ n+1$, for all $n ≥ 1$.

$f(n+1) = f(n) + f(1)$

$f(n) + f(1) ≤ n + f(1)$ by inductive hypothesis

$n + f(1) = n + 1$

q.e.d

There must be mistakes in there but where are they exactly?

All the best!

• The fact that $f(n+2) = f(n) + f(2)$ is in fact incorrect, by some distance. – астон вілла олоф мэллбэрг Nov 19 '17 at 6:32
• Please, typeset mathematical expressions using MathJax. – mucciolo Nov 19 '17 at 6:33
• If you are going to assume $f(n+2) = f(n) + f(2)$ you have to prove it. – fleablood Nov 19 '17 at 6:48
• I guess that I would have to prove that the function f is a homomorphism. But there must be another way. This was given as an exercise at some US university ( I am from Germany, not attending this university) and I am sure that the solution does not have to include a proof of the homomorphism. Could someone provide a proof, perhaps even with an explanation. All the best! – Maximilian Nov 19 '17 at 9:36
• Why don't you compute a few values? It's the biggest power of $2$ that is $\le n$ (in Java: Long.highestOneBit(n)), and you can prove that with strong induction. – Professor Vector Nov 19 '17 at 10:28

Use what the function IS. Don't just assume a property without validation.

And use strong induction.

Assume true for and $1\le n \le k$.

If $k+1$ is odd then: $f(k+1) = f(k+1-1)=f(k) \le k \le k+1$.

If $k+1$ is even then $f(k+1) = 2*f(\frac {k+1}2)$ And $\frac {k+1}2 \le \frac {k + k } 2 \le k$. So $f(\frac {k+1}2) \le \frac {k+1}2$. So $f(k+1) = 2*f(\frac {k+1}2) \le 2*\frac {k+1}2 = k+1$.

That's it.

But I must say that for whoever wrote this question, to give a function without a definition but only by a suggestion "..." example and then to expect a student to do a formal inductive (when the author than lack of induction definition was just fine) is rather terrible, if you ask me.

Would it have killed them to state;

$f(1) = 1$. For $n > 1$ then if $n$ is odd $f(n) = f(n-1)$ and if $n$ is even $f(n) = 2*f(\frac n2)$

?

• Thanks! That was very helpul. A precise answer without snark! – Maximilian Nov 20 '17 at 6:23
• Thanks! That was very helpul. A precise answer without snark! But was I right when I stated that the inductive hypothesis is "We assume that f(n) ≤ n holds" ? – Maximilian Nov 20 '17 at 6:38
• Yes, that is the induction hypothesis. – fleablood Nov 20 '17 at 19:38