-1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ The fact that $f(n+2) = f(n) + f(2)$ is in fact incorrect, by some distance. $\endgroup$ – астон вілла олоф мэллбэрг Nov 19 '17 at 6:32
  • $\begingroup$ Please, typeset mathematical expressions using MathJax. $\endgroup$ – mucciolo Nov 19 '17 at 6:33
  • $\begingroup$ If you are going to assume $f(n+2) = f(n) + f(2)$ you have to prove it. $\endgroup$ – fleablood Nov 19 '17 at 6:48
  • $\begingroup$ 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! $\endgroup$ – Maximilian Nov 19 '17 at 9:36
  • $\begingroup$ 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. $\endgroup$ – Professor Vector Nov 19 '17 at 10:28
1
$\begingroup$

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)$

?

$\endgroup$
  • $\begingroup$ Thanks! That was very helpul. A precise answer without snark! $\endgroup$ – Maximilian Nov 20 '17 at 6:23
  • $\begingroup$ 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" ? $\endgroup$ – Maximilian Nov 20 '17 at 6:38
  • $\begingroup$ Yes, that is the induction hypothesis. $\endgroup$ – fleablood Nov 20 '17 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.