We will use Mathematical induction to proove this. But here you dont just have to asume that its true for k and prove for k+1. Here we have to use the extended case of MI.
Assume is a statement that
Now show that , and is correct. (which infact is)
, and are true.
Now prove that is trure.
Now in a few step you can show that is true. hence proved.