Split your inductive step into two cases, one where k+1 is odd, and one where k+1 is even.

When k+1 is even, (k+1)/2 is a natural number and is less than k, so your inductive hypothesis holds for it. Therefore

as you defined, so

I'll leave the other case to you, good luck.