Is this induction valid?

Un = n^2+3n

Prove, Un is divisible by 2

Un = n^2+3n = 2m
=> 3n = 2m-n^2

Un+1 = (n+1)^2+3(n+1)
=> n^2+5n+4
=> n^2+2n+3n+4
=>n^2+2n+2m-n^2+4
=>2(n+m+2)

I assumed that Un was divisible by 2, so equal to 2m, where m is any integer and then used that to prove that Un+1 is divisible by 2. Is this fine for a FP1 exam?

Reply 1

steve10

I wouldn't think so. You have simply shown that IF Un is divisible by 2 then so also is Un+1.

Hint:try splitting the n^2 + 3n into two factors

Reply 2

Evgeny.Makarov

The induction step is correct. One may write it slightly shorter without introducing m: n^2+5n+4 = (n^2+3n) + 2(n + 2), and the first number is even by IH. Don't forget the base case.

Reply 3

Chwirkytheappleboy

You don't need to equate anything to 2m... just state that it's divisible by two and follow on from there

u_n = n^2+3n

u_n

is divisible by 2. Assume true for

n=k

u_k=k^2+3k

is divisible by 2

u_{k+1} = (k+1)^2+3(k+1) = k^2+5k+4 = (k^2+3k)+(2k+4)

since by our assumption,

(k^2+3k)

is divisible by 2, and clearly

(2k+4)

is divisible by 2, we can deduct that if

u_k

is divisible by 2, then so is

u_{k+1}

.

So we just need to show the first case.

u_1 = 4

which is divisible by 2, so the statement is true for all n greater than or equal to 1.

Do something similar for n = k-1

Reply 4

steve10

simpler.

Un = n^2 + 3n = n(n+3)

if n is odd, (n+3) is even and product is even
if n is even, then (n+3) is odd and product is even

Hence Un is even.

Reply 5

Chwirkytheappleboy

steve10

simpler.

Un = n^2 + 3n = n(n+3)

if n is odd, (n+3) is even and product is even
if n is even, then (n+3) is odd and product is even

Hence Un is even.

That is a good proof, but it's not proof by induction, so although it's correct it would attract no marks in an exam question about inductive proofs