I proved this identity back in school using Binet's formula(without induction) and some identities.
Do you have to use induction?. That is a good way to go, but I like this method I stumbled onto a while back while studying Fibonacci's for a class called Seminars in Mathematics. I doubt if it's original, but it works.
I will use
Take note that and and
We will use these later.
From Binet's formula:
We can sub it in our formula to prove:
Expand:
Group and factor:
Take note that everything inside the brackets is 0, due to the identities previously mentioned.
We get:
,
You can show various identities using these tools. They can be handy to know.