Trees

Quote:

Originally Posted by Tom101

Prove the following by induction on n

1+5+9+....+(4n-3) = n(2n-1) for all n => 1

check base case n=1

1=1(2(1)-1) true

assume n=k

$1+5+9+....+(4k-3)=k(2k-1)$

Show k+1

$1+5+9+....+(4k-3)+[4(k+1)-3]=$
by the induction hypothsis
$k(2k-1)+[4(k+1)-3]=2k^2-k+4k+4-3=2k^2+3k+1=$

$(k+1)(2k+1)=(k+1)(2(k+1)-1)$

The last one is k+1

QED