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...