-2
$\begingroup$

Given a statement $P(n)$ about the natural numbers, demonstrate how a proof of it by complete induction can be rewritten using simple induction.

  • 3
    welcome to MathS$E$. I see that this is your first question. So I wanted to let you know a few things about MathSE. We like to know the sources of questions. We also like to know what you've tried on a problem. These sort of pleasantries usually result in more and better answers. Finally, I should add that posting questions in the imperative (i.e. Compute all such, Prove that...) is considered rude by some of the members, so it would be nice of you to change that wording. Thank you.2011-09-20

2 Answers 2

5

HINT. Let $R(n)$ be the property "$P(k)$ holds for all $k\leq n$".

4

I'm not sure the formulation of this question is appropriate, but I will answer anyway.

I shall assume $P(0)$ is proved.

"Proving $P(n)$ for all $n$ by complete induction" means to prove $P(0) \wedge P(1) \wedge \dots P(n) \implies P(n+1)$. "Proving $P(n)$ for all $n$ by simple induction" means to prove $P(n) \implies P(n+1)$.

Now simply set Q(n) = `P(0), P(1), \dots, P(n) \text{ all hold}'. Clearly proving $Q(n) \implies Q(n+1)$ (simple induction) is the same as proving the complete induction statement above.