# Proof by induction [closed]

I was just wondering how to prove generally that a statement is true

i think this is correct, but i am not sure:

1) prove that the statement $P$ is true for $1$

2) and then prove that the statement is true for $P(n+1)$, by taking for granted that $P(n)$ is true.

2.5) we can prove that $P(n+1)$ is true by showing that it is true when $n = 1$.

i am not sure about the last part though.

-

## closed as not a real question by Andres Caicedo, Austin Mohr, TMM, Norbert, Ｊ. M.Nov 17 '12 at 12:46

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, see the FAQ.

## 3 Answers

This is axiom 9 of Peano arithmetic. It is the hard one. Is that the system you are working in?

-
 no, i am taking an introductory course – George Nov 16 '12 at 5:52 seriously, how is that an answer to my question? – George Nov 16 '12 at 6:04 My point is that it is an axiom. You don't have to prove it is true, you use it to prove other things are true. Intuitively, it says if you know $P(1),$ and $P(1) \implies P(2)$, you know $P(2)$. Then if $P(2) \implies P(3)$ you know $P(3)$ and so on. If you can prove that in general $P(n) \implies P(n+1)$ you know $P(n)$ for all $n$. – Ross Millikan Nov 16 '12 at 14:11 i know that, but how do i prove that p(n+1) is true? i can't do any algebraic manipulation. – George Nov 16 '12 at 16:03

2.5) By the Principle of mathematical induction, P(n) is true for the condition given. eg. all natural numbers of n.

-
 how do you prove that? – George Nov 16 '12 at 5:53 like i must show that a|n, but i can't simplify the expression further to be able to replace (n+1) by n. – George Nov 16 '12 at 5:54

Part 2.5 is not true: Take $P(n)$ to mean "$n=1\text{ or }n=2$". Now $P(1)$ is true. $P(n+1)$ is also true when $n=1$. However, it does not follow that $P(n)$ is true for all $n$ since $P(3)$ is not true.

-