1
$\begingroup$

I am totally stumped by this question. I have proved the base case. Then for $k$ is $1$ assume the relation to be true. When I try to prove for $k+1$, the terms just do not simplify to what I want. Is there something missing in the question or is it that I am just not being able to solve the question?

$\endgroup$
5
  • $\begingroup$ What are the base values of F ? $\endgroup$
    – Shailesh
    Commented Sep 14, 2015 at 3:56
  • $\begingroup$ Oh these are for fibonacci numbers. $\endgroup$
    – 277roshan
    Commented Sep 14, 2015 at 3:56
  • $\begingroup$ You can use second principle of finite induction. Use two previous relations to prove the third $\endgroup$
    – Shailesh
    Commented Sep 14, 2015 at 4:03
  • $\begingroup$ It seems like the terms get as big as F(2k+4) if I am taking k, k+1 and solving for k+2. While trying to solve the process seems quite convoluted. I still cannot get to the solution. $\endgroup$
    – 277roshan
    Commented Sep 14, 2015 at 4:17
  • $\begingroup$ See also: math.stackexchange.com/questions/509266/… $\endgroup$ Commented Nov 7, 2015 at 20:05

2 Answers 2

1
$\begingroup$

We have $F_{n}F_{n+1} - F_{n-2}F_{n-1} = F_{2n-1}$ (See link).

Assume that $F_{2k} = F_k(F_{k-1}+F_{k+1})$.

We prove that $$F_{2(k+1)} = F_{k+1}(F_{k} + F_{k+2}).$$

One has $$F_{2(k+1)} = F_{2k+1} + F_{2k} = F_k(F_{k-1}+F_{k+1}) + F_{k+1}F_{k+2} - F_{k-1}F_{k} = F_{k+1}(F_k+F_{k+2}).$$

$\endgroup$
0
0
$\begingroup$

Assume that $F_{2n} = F_n[F_{n-1}+F_{n+1}]$ and use this (the n case) to show that the n+1 case, i.e. $F_{2(n+1)} = F_{2n+2} = F_{n+1}[F_n+F_{n+2}]$, is true

We have $F^2_{n+1}-F_nF_{n+2} = (-1)^n$

$F_{n+1}[F_n+F_{n+2}]$

= $F_{n+1}F_n+F_{n+1}F_{n+2}$

= $F_{n+1}F_n+F^2_{n+1} + F_{n+1}F_n$ since $F_{n+2} = F_{n+1}+ F_n$ for fibonacci numbers

= $(-1)^n + F_nF_{n+2} + 2F_nF_{n+1}$

= $(-1)^n + F_nF_{n+1} + F^2_n + 2F_nF_{n+1}$

= $(-1)^n + F_nF_{n+1} + F_{n-1}F_{n+1} + (-1)^{n-1} + 2F_nF_{n+1}$

= $F_nF_{n+1} + F^2_{n-1} + F_{n-1}F_n + 2F_nF_{n+1}$

= $F_nF_{n+1} + F_{n-2}F_n + (-1)^{n-2}+ F_{n-1}F_n + 2F_nF_{n+1}$

= $3F_nF_{n+1} + F_{n-2}F_n + (-1)^{n-2}+ F_{n-1}F_n$

= $3F_nF_{n+1} + F_{n-2}F_{n+1} - F_{n-2}F_{n-1} + (-1)^{n-2}+ F_{n-1}F_n$ since $F_n = F_{n+1}-F_{n-1}$

= $3F_nF_{n+1} + F_nF_{n+1} - F_{n-1}F_{n+1} - F_{n-2}F_{n-1} + (-1)^{n-2}+ F_{n-1}F_n$

= $3F_nF_{n+1} + F^2_n + F_nF_{n-1}- F_{n-2}F_{n-1} + (-1)^{n-2}+ F_{n-1}F_n$ since $F_n = F_{n+1}-F_{n-1}$

= $3F_nF_{n+1} + 2F_nF_{n-1} - F_{n-1}F_{n-2} + F_{n-1}F_{n+1} -F_{n-1}F_{n+1} + (-1)^{n-1} + (-1)^{n-2}$

= $3F_nF_{n+1} + 2F_nF_{n-1} - F_{n-1}F_{n-2}$

= $3F_nF_{n+1}+ 3F_nF_{n-1} - F_nF_{n-1}- F_{n-1}F_{n-2}$

= $3F_n(F_{n+1}+F_{n-1})- F_nF_{n-1}- F_{n-1}F_{n-2}$

= $3F_{2n} - F_{n-1}[F_n+ F_{n-2}]$ using our induction hypothesis

= $3F_{2n} - F_{2(n-1)}$

= $2F_{2n} + F_{2n-1}$ since $F_{2n}-F_{2(n-1)} = F_{2n-1} (F_{2(n-1)}=F_{2n-2)}$

= $F_{2n} + F_{2n+1}$ since $F_{2n+1} = F_{2n} + F_{2n-1}$

= $F_{2n+2} = F_2{n+1}$

Since we have shown that $F_n+1[F_(n)+F_(n+2)] = F_2(n+1)$ (the n+1 case) is true from assuming the n case $F_2n = F_n[F_(n-1)+F_(n+1)]$ to be true and we know that the base case n=1 is true, we have proven $F_2n = F_n[F_(n-1)+F_(n+1)]$ inductively.

$F^2_n+1-F_nF_n+2 = (-1)^n$ can be proven pretty quickly by induction. I could not solve this problem either without the above identity.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .