To prove it for $n=1$ you just need to verify that
$ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0 \end{array} \right)^1 $ =
$ \left( \begin{array}{ccc}
F_2 & F_1 \\
F_1 & F_0 \end{array} \right) $
which is trivial.
After you established the base case, you only need to show that assuming it holds for $n$ it also holds for $n+1$.
So assume
$ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0 \end{array} \right)^n $ =
$ \left( \begin{array}{ccc}
F_{n+1} & F_n \\
F_n & F_{n-1} \end{array} \right) $
and try to prove
$ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0 \end{array} \right)^{n+1} $ =
$ \left( \begin{array}{ccc}
F_{n+2} & F_{n+1} \\
F_{n+1} & F_n \end{array} \right) $
Hint: Write $ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0 \end{array} \right)^{n+1} $ as $ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0 \end{array} \right)^n $$ \left( \begin{array}{ccc}
1 & 1 \\
1 & 0 \end{array} \right) $.
General term: $s_n = \displaystyle \sum_{0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-r}{r} \text{ for } n \in \mathbb{N} \tag{1}$
I think you struggled because the binomial sum $s_{n+2}$ has a decomposition that involves both its even and odd numbered predecessors, and not just any one of them, as you were trying in the inductive step.
Decomposition: $s_{n+2} = s_{n+1} + s_{n} \tag{2}$
This is easy to prove by using the combinatorial identity $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$. See here and here.
We can then use this property along with strong induction to prove:
$P(n): s_n = \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^n \text{ true } \forall n \in \mathbb{N}\tag{3}$
Proof-sketch:
Base case: Show $P(1)$ and $P(2)$ to be true (by evaluating both sides).
Inductive step: Assume $P(n)$ and $P(n+1)$ true.
Then $\begin{aligned}s_{n+2} & = s_{n+1} + s_{n} \\ & = \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n+1} - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^{n+1} + \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^n \\ & = \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^n\left(\frac{3 + \sqrt{5}}{2}\right) - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^n\left(\frac{3 - \sqrt{5}}{2}\right) \\ & = \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n+2} - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^{n+2} \\ & \implies P(n+2) \text{ true }\end{aligned}$
This completes our proof. $ \blacksquare$
Note: The formulas for odd $n$ and even $n$ follow automatically from $(3)$ by the removal of the floor function in $s_n$.
Best Answer
First, define the Fibonacci numbers:
Let $F_n$ be the sequence of Fibonacci numbers, given by
$$F_0 = 0, F_1 = 1, \text{ and}\quad F_n = F_{n-1} + F_{n-2}\; \text{ for}\; n \geq 2.$$
Hints:
$(1)$ Use the definition of $F_n$.
$(2)$ You can use the following good-to-know identities:
Note that the above identities follow from the more general identity:
Proof of $(I)$:
Fix $n \in \mathbb{N}$. We shall use induction on $m$. For $m=1$, the right-hand side of the equation becomes $$F_{n-1}F_{1} + F_{n}F_{2} = F_{n-1} + F_{n},$$ which is equal to $F_{n+1}$. When $m=2$, the equation is also true.( I hope you can prove this!).
Now assume, that the result is true for $k=3,4, \cdots , m$. We want to show that the result is true for $k=m+1$. $$ \text{For} \ k=m-1 \ \text{we have} \quad F_{n+m-1} = F_{n-1}F_{m-1} + F_{n}F_{m},\,\text{ and}$$ $$ \text{For} \ k = m \ \text{we have} \quad F_{m+n}=F_{n-1}F_{m} + F_{n}F_{m+1}$$ Adding both the sides you will get $$F_{m+n-1} + F_{m+n} = F_{m+n+1} = F_{n-1}F_{m+1} + F_{n}F_{m+2},$$ $$\text{so,}\;\; F_{m+n}=F_{n-1}F_m + F_{n}F_{m+1}$$
Identities (i) and (ii) follow from $(I)$ by putting $m = n$ and manipulating the expressions.