Discrete Mathematics Inductive Proofs Discrete Mathematics

Discrete Mathematics - Inductive Proofs

Discrete Mathematics - Inductive Proofs 40. Given a0 = 3 and an+1= 2an+ n^2 -n + 1, list the terms a0 through a5, and then show that for every n we have an = 3.(2^n+1-1)-n(n + 1).

Solution

a0 =3

a_n+1 = 2a_n+(n²-n+1)

a1 = 6+1 =7

a2 = 14+1 =15

a3 = 30+3 =33

a4 = 66+7 =73

a5 = 146+13 =159

-------------------------------

In general an = 2an+n^2-n+1

= 2[an-1+(n-1)²-(n-1)+1]+n^2-n+1

Let us prove by induction.

For n =2

a2 = 3(4-1)-2 = 7

Let this be true for n =k

i.e. ak = 3(2^k+1-1) -k(k+1)

Consider a_{k+1 =} 2ak+k²-k+1 (by recurrence formula given)

Substitute for ak

a_{k+1 =} 2[3(2^k+1-1) -k(k+1)]+k²-k+1

= 3(2^k+2-1)-3-2k^2-2k+k^2-k+1

= 3(2^k+2-1)-(k^2+3k+2)

=  3(2^k+2-1)-(k+1)(k+2)

Thus if true for n =k, it is true for n = k+1

Hence proved for all natural numbers.