first let's start by checking the base case n = 1:
now let us assume that the relation holds for some n:
now if we prove that the relation holds for n+1, then by the induction hypothesis the relation is true for any n,
thus we have to prove that:
our next step is to use the given recurrence relation, since it is true for every n it must be true in particular for 2n-1:
for the same reason it must be true for 2n, so we get:
substitute 1) into 2) and then 2) into 3), and you;ll complete your proof...