Proof by Induction #$1$

Show each part of a proof by induction of the following fact for all positive integers n:

Xn

j$=1$

$2$j $=$ n$($n $+1)$

Follow the proof blueprint below, marking each step:

$1.$ Define the predicate P$($n$)$ s$.$t$.$ the theorem above is of the form $$n$1$ P$($n$).$

$2.$ State the base case of this proof, i$.$e$.$ state what must be proven in the base case.

$3.$ Prove that the base case holds. $($This could be very easy, but it$$s still a proof.$)$

$4.$ State what what needs to be proven in the inductive step of the proof. $($If you like you

can use predicate P to state this.$)$

$5.$ Prove the statement you stated above, i$.$e$.$ complete the inductive step of the proof. In

your proof, identify clearly what is the inductive hypothesis, i$.$e$.$ the inductive assumption,

and identify clearly the step in the proof where you use this inductive hypothesis.