# Thread: Rigorously Prove (Number proofs)

1. ## Rigorously Prove (Number proofs)

Above question coming from a past paper. It carries almost a third of the exam marks. I worked it out by substituting Succ (k) during inductive step for k', called in the Inductive Hypothesis and resubstituted for Succ k to match LHS. It took all of 8 lines and it seems that's nowhere near enough to earn 30 marks during an exam. Is that a rigorous method, and how would it be done if not? The exam will be open book and we can quote any of the many rules available to us (like commutativity and associativity of addition).

2. ## Re: Rigorously Prove (Number proofs)

what does this mean?

$\displaystyle \forall n,m:\mathbb{N}\cdot n\oplus m=(n+n)+m$

3. ## Re: Rigorously Prove (Number proofs)

LHS = RHS I suppose. It needs to be proved, typically using Induction and the definition provided in the question.

I went with Inductive Hypothesis: $\displaystyle k \oplus m=(k+k)+m$

Inductive Case was $\displaystyle Succ(k) \oplus m = (Succ(k) + Succ(k) ) + m$ (Where Succ(k) stands for Successor, in other words k+1)

I said let $\displaystyle Succ(k) = k'$

$\displaystyle k'+k'+m$
{IH}
$\displaystyle k' \oplus m$
{By replacement}
$\displaystyle Succ(k) \oplus m$
$\displaystyle = LHS$

Seems like it's not particularly rigorous to straight up use the IH and resolve immediately.

4. ## Re: Rigorously Prove (Number proofs)

Given from book Lemma, how reasonable would this solution instead be:

$\displaystyle \forall n,m:\mathbb{N}\cdot Successor (n) + m = Successor (n+m)$

$\displaystyle (Succ(k)+Succ(k)) + m$
{Bracket associativity}
$\displaystyle (Succ(k)+Succ(k)+m)$
{Lemma}
$\displaystyle (Succ(k)+Succ(k + m)$
{Lemma}
$\displaystyle (Succ(k)+ k + Succ(m))$
{Lemma}
$\displaystyle (Succ(k+k) + Succ(m))$
{Lemma}
$\displaystyle (Succ(k+k+Succ(m)))$
{Inductive Hypothesis}
$\displaystyle (Succ(k \oplus Succ(m))$
{2nd definition}
$\displaystyle Succ(k) \oplus m$
$\displaystyle =LHS$