2

I have encountered several problems where one can prove the desired result without actually needing the induction hypothesis. More specifically, you basically just pick $n \in \mathbb{N}$ and run through the argument. In fact, the solution manual does exactly this (without breaking the problem in steps). What caused me some concern is that I encountered a problem where I can prove the desired result just picking arbitrary $n$, but I can prove it in a manner when I explicitly use the induction hypothesis. What does it mean when you don't actually need the induction hypothesis? Please help!

Here's the problem: Prove that for $p_{k} \geq 0$ and $\sum^{n}_{k=1} p_{k} = 1$, if $g(x) = \sum^{n}_{k=1} p_{k} \cos(\beta_{k}x)$, then $g^{2}(x) \leq \frac{1}{2} (1+ g(2x))$. We use the fact that if $f(x)= \cos(\beta x)$, then $f^{2}(x)= \frac{1}{2}(1+f(2x))$.

tchil9
  • 21
  • 1
    What's the problem? Your main phrase "I can prove it in a manner when I explicitly use the induction hypothesis" is not clear . What manner? It seems you do use the inductive hypothesis. – Marc van Leeuwen Oct 01 '14 at 04:00

2 Answers2

2

When you don't need to use the induction hypothesis, it means that you don't need to use induction. You can just do a direct proof.

Yuval Filmus
  • 57,157
  • 2
    Note there is one (and as far as I can see only one) exception to this, though it is probably not this that is bothering OP. If straight from the Peano axioms you want to prove that each natural number is either equal to $0$ or the successor of another natural number, then a trivial induction proves this: it is true for $0$ and [if true for $n$] it is true for $S(n)$; the bracketed part is the induction hypothesis which is unused here. Yet there is no proof without using induction. – Marc van Leeuwen Oct 01 '14 at 04:09
1

I guess “Proving (by induction) of a hypothesis by just considering an arbitrary n (only)” or “cross(ing) out the entire beginning of the proof” means “without testing the truth of the hypotheses when n = 1”.

This is fatal!

Let me demonstrate this by a counter-example:

Suppose that we have the following hypothesis:-

$H(n): \sum_{i=1}^n i^3 = [\frac {1}{2} n(n+1)]^2 + L$ ; where L is any arbitrary number.

Of course, this is not difficult to see that

If $H(k)$ is true, then

$H(k+1) = \sum_{i=1}^k i^3 + (k+1)^3$

$= [\frac {1}{2} k(k+1)]^2 + (k+1)^3 + L$

$= … = [\frac {1}{2} (k+1)(k+2)]^2 + L$; meaning $H(k+1)$ is also true.

However, obviously, $H(n)$ is definitely a false statement.

The key-point lies in the fact that the testing of $H(0)$ has been skipped.

Mick
  • 17,141