nyuuzyou/wikis huggingface dataset:
Fibonacci Nim/Examples/11

== Example of Game of Fibonacci Nim ==
Let a game of Fibonacci nim between player $\text A$ and player $\text B$ have a starting pile of $11$ counters.
$\text A$ removes $3$ counters, leaving $8$.
$\text B$ may remove up to $6$ counters, and takes $1$, leaving $7$.
$\text A$ may remove $1$ or $2$ counters, and takes $2$, leaving $5$.
$\text B$ may remove up to $4$ counters, and takes $1$, leaving $4$.
$\text A$ may remove $1$ or $2$ counters, and takes $1$, leaving $3$.
$\text B$ must remove either $1$ or $2$ counters, leaving $\text A$ in a position to take all the counters next turn.
$\text A$ wins.
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $37$
Category:Fibonacci Nim
Fibonacci Number/Sequence

== Sequence of Fibonacci Numbers ==
The sequence of Fibonacci numbers begins:
:$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, \ldots$
== Also defined as ==
== Sources ==
* : $5$
* : Tables: $3$ The First $40$ Fibonacci Numbers
* : Liber Abaci: $88$
* : $5$
* : Tables: $3$ The First $40$ Fibonacci Numbers
* : $\S 1.2.1$: Mathematical Induction
* : $\S 1.2.8$: Fibonacci Numbers: $(1)$
* 
* 
* : Chapter $4$: Lure of the Unknown: Cubic equations
* 
Category:Fibonacci Numbers
Fibonacci Number/Sequence/Negative

== Sequence of Fibonacci Numbers for Negative Index ==
The sequence of Fibonacci numbers for negative index begins:
:$\ldots, 89, -55, 34, -21, 13, -8, 5, -3, 2, -1, 1, 0$
== Sources ==
* 
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $8$
Category:Fibonacci Numbers
Fibonacci Number 2n equals Fibonacci Number n by Lucas Number n

== Theorem ==
Let $F_n$ denote the $n$th Fibonacci number.
Let $L_n$ denote the $n$th Lucas number.
Then:
:$F_{2 n} = F_n L_n$
== Proof ==
Let:
:$\phi = \dfrac {1 + \sqrt 5} 2$
:$\hat \phi = \dfrac {1 - \sqrt 5} 2$
Then:
== Sources ==
* : $11$
* : $11$
Category:Fibonacci Numbers
Category:Lucas Numbers
Fibonacci Number 3n in terms of Fibonacci Number n and Lucas Number 2n

== Theorem ==
Let $F_n$ denote the $n$th Fibonacci number.
Let $L_n$ denote the $n$th Lucas number.
Then:
:$F_{3 n} = F_n \paren {L_{2 n} + \paren {-1}^n}$
== Proof ==
Let:
:$\phi = \dfrac {1 + \sqrt 5} 2$
:$\hat \phi = \dfrac {1 - \sqrt 5} 2$
Then:
Then we note:
The result follows.
== Sources ==
* : $11$
* : $11$
Category:Fibonacci Numbers
Category:Lucas Numbers
Fibonacci Number as Sum of Binomial Coefficients

== Theorem ==
Let $F_n$ denote the $n$th Fibonacci number.
Then:
where:
:$\dbinom a b$ denotes a binomial coefficient
:$\floor x$ denotes the floor function, which is the greatest integer less than or equal to $x$.
== Proof ==
By definition of Fibonacci numbers:
:$F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, \ldots$
The proof proceeds by induction.
For all $n \in \Z_{>0}$, let $\map P n$ be the proposition:
:$\ds F_n = \sum_{k \mathop = 0}^{\floor {\frac {n - 1} 2} } \dbinom {n - k - 1} k$
=== Basis for the Induction ===
$\map P 1$ is the case:
So $\map P 1$ is seen to hold.
$\map P 2$ is the case:
So $\map P 2$ is also seen to hold.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P {k - 1}$ and $\map P k$ are true, where $k > 2$ is an even integer, then it logically follows that $\map P {k + 1}$ and $\map P {k + 2}$ are both true.
So this is our induction hypothesis:
:$\ds F_{k - 1} = \sum_{i \mathop = 0}^{\frac k 2 - 1} \dbinom {k - i - 2} i$
:$\ds F_k = \sum_{i \mathop = 0}^{\frac k 2 - 1} \dbinom {k - i - 1} i$
Then we need to show:
:$\ds F_{k + 1} = \sum_{i \mathop = 0}^{\frac k 2} \dbinom {k - i} i$
:$\ds F_{k + 2} = \sum_{i \mathop = 0}^{\frac k 2} \dbinom {k - i + 1} i$
=== Induction Step ===
This is our induction step:
For the first part:
For the second part:
So $\map P {k - 1} \land \map P k \implies \map P {k + 1} \land \map P {k + 2}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\ds \forall n \in \Z_{>0}: F_n = \sum_{k \mathop = 0}^{\floor {\frac {n - 1} 2} } \dbinom {n - k - 1} k$
== Examples ==
== Historical Note ==
== Sources ==
* : $\text {3-1}$ Permutations and Combinations: Exercise $13$
* : $5$
* : $5$
:::but note the misprint in the statement of the result.
Category:Fibonacci Numbers
Category:Binomial Coefficients
Category:Proofs by Induction
Category:Fibonacci Number as Sum of Binomial Coefficients
Fibonacci Number as Sum of Binomial Coefficients/Mistake/First Edition

== Source Work ==
:
:The Dictionary
:: $5$
== Mistake ==
: discovered a relationship between Fibonacci numbers and the binomial coefficients:
::$F_{n + 1} = \paren {\dfrac n 0} + \paren {\dfrac {n - 1} 1} + \paren {\dfrac {n - 2} 2} + \cdots$
:For example:
== Correction ==
The notation is wrong.
It should read:
: discovered a relationship between Fibonacci numbers and the binomial coefficients:
::$F_{n + 1} = \dbinom n 0 + \dbinom {n - 1} 1 + \dbinom {n - 2} 2 + \cdots$
:For example:
The notation was corrected for the second edition of , but a further mistake was introduced in its place.
== Sources ==
* : $5$
Category:Mistakes/Curious and Interesting Numbers
Fibonacci Number as Sum of Binomial Coefficients/Mistake/Second Edition

== Source Work ==
:
:The Dictionary
:: $5$
== Mistake ==
: discovered a relationship between Fibonacci numbers and the binomial coefficients:
::$F_{n + 1} = \dbinom n 0 + \dbinom {n - 1} 1 + \dbinom {n - 2} 1 + \cdots$
== Correction ==
The given expression is a misprint for:
::$F_{n + 1} = \dbinom n 0 + \dbinom {n - 1} 1 + \dbinom {n - 2} 2 + \cdots$
Interestingly and oddly, this is correct in the first edition of of $1986$.
== Sources ==
* : $5$
Category:Mistakes/Curious and Interesting Numbers
Fibonacci Number by Golden Mean plus Fibonacci Number of Index One Less

== Theorem ==
Let $n \in \Z$.
Then:
:$\phi^n = F_n \phi + F_{n - 1}$
where:
:$F_n$ denotes the $n$th Fibonacci number
:$\phi$ denotes the golden mean.
== Proof ==
=== Positive Index ===
First the result is proved for positive integers.
=== Negative Index ===
Then the result is extended to negative integers.
Hence the result is seen to show for both positive and negative integers.
== Also see ==
* Fibonacci Number by One Minus Golden Mean plus Fibonacci Number of Index One Less
== Sources ==
* 
* : $1 \cdotp 61803 \, 39887 \, 49894 \, 84820 \, 45868 \, 34365 \, 63811 \, 77203 \, 09179 \, 80576 \ldots$
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $11$
* : $1 \cdotp 61803 \, 39887 \, 49894 \, 84820 \, 45868 \, 34365 \, 63811 \, 77203 \, 09179 \, 80576 \ldots$
Category:Fibonacci Numbers
Category:Golden Mean
Category:Fibonacci Number by Golden Mean plus Fibonacci Number of Index One Less
Fibonacci Number by Golden Mean plus Fibonacci Number of Index One Less/Negative Index

== Theorem ==
Let $n \in \Z_{\le 0}$.
Then:
:$\phi^n = F_n \phi + F_{n - 1}$
where:
:$F_n$ denotes the $n$th Fibonacci number as extended to negative indices
:$\phi$ denotes the golden mean.
== Proof ==
The proof proceeds by induction.
For all $n \in \Z_{\le 0}$, let $\map P n$ be the proposition:
:$\phi^n = F_n \phi + F_{n - 1}$
This can equivalently be expressed as:
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\phi^{-n} = F_{-n} \phi + F_{-n - 1}$
$\map P 0$ is the case:
Thus $\map P 0$ is seen to hold.
==== Basis for the Induction ====
$\map P 1$ is the case:
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
==== Induction Hypothesis ====
Now it needs to be shown that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:$\phi^{-k} = F_{-k} \phi + F_{-k - 1}$
from which it is to be shown that:
:$\phi^{-\paren {k + 1} } = F_{-\paren {k + 1} } \phi + F_{-\paren {k + 1} - 1}$
==== Induction Step ====
This is the induction step:
So $\map P k \implies \map P {k + 1}$ and it follows by the Principle of Mathematical Induction that:
:$\forall n \in \Z_{\le 0}: \phi^n = F_n \phi + F_{n - 1}$
Category:Fibonacci Number by Golden Mean plus Fibonacci Number of Index One Less
Fibonacci Number by Golden Mean plus Fibonacci Number of Index One Less/Positive Index

== Theorem ==
Let $n \in \Z_{\ge 0}$.
Then:
:$\phi^n = F_n \phi + F_{n - 1}$
where:
:$F_n$ denotes the $n$th Fibonacci number
:$\phi$ denotes the golden mean.
== Proof ==
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $P \left({n}\right)$ be the proposition:
:$\phi^n = F_n \phi + F_{n - 1}$
$P \left({0}\right)$ is the case:
Thus $P \left({0}\right)$ is seen to hold.
==== Basis for the Induction ====
$P \left({1}\right)$ is the case:
Thus $P \left({1}\right)$ is seen to hold.
This is the basis for the induction.
==== Induction Hypothesis ====
Now it needs to be shown that, if $P \left({k}\right)$ is true, where $k \ge 1$, then it logically follows that $P \left({k + 1}\right)$ is true.
So this is the induction hypothesis:
:$\phi^k = F_k \phi + F_{k - 1}$
from which it is to be shown that:
:$\phi^{k + 1} = F_{k + 1} \phi + F_k$
==== Induction Step ====
This is the induction step:
So $P \left({k}\right) \implies P \left({k + 1}\right)$ and it follows by the Principle of Mathematical Induction that:
:$\forall n \in \Z_{\ge 0}: \phi^n = F_n \phi + F_{n - 1}$
Category:Fibonacci Number by Golden Mean plus Fibonacci Number of Index One Less
Fibonacci Number by One Minus Golden Mean plus Fibonacci Number of Index One Less

== Theorem ==
Let $n \in \Z$.
Then:
:$\hat \phi^n = F_n \hat \phi + F_{n - 1}$
where:
:$F_n$ denotes the $n$th Fibonacci number
:$\hat \phi$ denotes the $1$ minus the golden mean:
::$\hat \phi := 1 - \phi$
== Proof ==
== Also see ==
* Fibonacci Number by Golden Mean plus Fibonacci Number of Index One Less
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $11$
Category:Fibonacci Numbers
Category:Golden Mean
Category:Fibonacci Number by One Minus Golden Mean plus Fibonacci Number of Index One Less
Fibonacci Number by Power of 2

== Theorem ==
where:
:$F_n$ denotes the $n$th Fibonacci number
:$\dbinom n {2 k + 1} \ $ denotes a binomial coefficient.
== Proof 1 ==
== Proof 2 ==
== Also presented as ==
This result can also be seen presented as:
:$\ds 2^n F_n = 2 \sum_{k \text { odd} } \dbinom n k 5^{\paren {k - 1} / 2}$
== Historical Note ==
== Sources ==
* : $5$
* : $5$
Category:Fibonacci Numbers
Category:Binomial Coefficients
Category:Fibonacci Number by Power of 2
Fibonacci Number by Power of 2/Proof 1

== Theorem ==
== Proof ==
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\ds 2^{n - 1} F_n = \sum_k 5^k \dbinom n {2 k + 1}$
First note the bounds of the summation.
By definition, $\dbinom n k = 0$ where $k < 0$ or $k > n$.
Thus in all cases in the following, terms outside the range $0 \le k \le n$ can be discarded.
$\map P 0$ is the case:
Thus $\map P 0$ is seen to hold.
=== Basis for the Induction ===
$\map P 1$ is the case:
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P r$ is true, where $r \ge 1$, then it logically follows that $\map P {r + 1}$ is true.
So this is the induction hypothesis:
:$\ds 2^{r - 1} F_r = \sum_k 5^k \dbinom r {2 k + 1}$
from which it is to be shown that:
:$\ds 2^r F_{r + 1} = \sum_k 5^k \dbinom {r + 1} {2 k + 1}$
=== Induction Step ===
This is the induction step:
So $\map P r \implies \map P {r + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \Z_{\ge 0}: \ds 2^{n - 1} F_n = \sum_k 5^k \dbinom n {2 k + 1}$
== Historical Note ==
Category:Fibonacci Number by Power of 2
Fibonacci Number by Power of 2/Proof 2

== Theorem ==
== Proof ==
Setting $j = 2 k + 1$ for $0 \le k \le \paren {j - 1} / 2$ gives:
:$\ds \sum_{k \mathop \ge 0} \binom n {2 k + 1} 5^k$
and the limits of the index of the summation are irrelevant, as $\dbinom n {2 k + 1} = 0$ for $j < 0$ and $j > n$.
Hence the result.
== Historical Note ==
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $25$
Category:Fibonacci Number by Power of 2
Fibonacci Number equal to Sum of Sequence of Cubes

== Theorem ==
The following Fibonacci number can be expressed as the sum of a sequence of cubes:
:$F_{18} = 2584 = 7^3 + 8^3 + 9^3 + 10^3$
== Proof ==
== Historical Note ==
== Sources ==
* : $2584$
Category:Fibonacci Numbers
Category:Cube Numbers
Category:2584
Fibonacci Number greater than Golden Section to Power less Two

== Theorem ==
For all $n \in \N_{\ge 2}$:
:$F_n \ge \phi^{n - 2}$
where:
:$F_n$ is the $n$th Fibonacci number
:$\phi$ is the golden section: $\phi = \dfrac {1 + \sqrt 5} 2$
== Proof ==
The proof proceeds by induction.
For all $n \in \N_{\ge 2}$, let $\map P n$ be the proposition:
:$F_n \ge \phi^{n - 2}$
=== Basis for the Induction ===
$\map P 2$ is true, as this just says:
:$F_2 = 1 = \phi^0 = \phi^{2 - 2}$
It is also necessary to demonstrate $\map P 3$ is true:
:$F_3 = 2 \ge \dfrac {1 + \sqrt 5} 2 = \phi = \phi^{3 - 2}$
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P j$ is true for all $2 \le j \le k$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:$F_j \ge \phi^{j - 2}$ for $2 \le j \le k$
from which it is to be shown that:
:$F_{k + 1} \ge \phi^{k - 1}$
=== Induction Step ===
This is the induction step:
As we have already shown $\map P 2$ and $\map P 3$, we just need to prove the result for $k \ge 3$.
So $\map P 2 \land \map P 3 \land \dots \land \map P k \implies \map P {k + 1}$ and the result follows by the Second Principle of Mathematical Induction.
Therefore:
:$\forall n \in \N_{\ge 2}: F_n \ge \phi^{n - 2}$
== Also see ==
* Fibonacci Number less than Golden Section to Power less One
== Sources ==
* : $\S 1.2.1$: Mathematical Induction: Exercise $4$
Category:Fibonacci Numbers
Category:Golden Mean
Fibonacci Number in terms of Larger Fibonacci Numbers

== Theorem ==
Let $F_k$ be the $k$th Fibonacci number.
Then:
:$\forall m, n \in \Z_{>0} : \paren {-1}^n F_{m - n} = F_m F_{n - 1} - F_{m - 1} F_n$
== Proof ==
Category:Fibonacci Numbers
Fibonacci Number is not Product of Two Smaller Fibonacci Numbers

== Theorem ==
Let $m, n \in \Z$ be integers.
Suppose $\size m, \size n \ge 3$.
Let $F_m$ and $F_n$ be the $m$th and $n$th Fibonacci numbers.
Then $F_m \times F_n$ is not a Fibonacci number.
== Proof ==
From Honsberger's Identity:
:$F_n = F_{k - 1} F_{n - k + 2} + F_{k - 2} F_{n - k + 1}$
for $2 \le k \le n$.
 $F_n = F_m F_k$ for some $m, k \ge 3$.
Then:
The is a weighted mean of $2$ consecutive Fibonacci numbers.
Thus:
:$F_{n - k + 2} < F_m < F_{n - k + 1}$
which cannot happen.
The result follows by Proof by Contradiction.
== Sources ==
* 
* : $5$
Category:Fibonacci Numbers
Fibonacci Number less than Golden Section to Power less One

== Theorem ==
For all $n \in \N_{> 0}$:
:$F_n \le \phi^{n - 1}$
where:
:$F_n$ is the $n$th Fibonacci number
:$\phi$ is the golden section: $\phi = \dfrac {1 + \sqrt 5} 2$
== Proof ==
The proof proceeds by induction.
For all $n \in \N_{> 0}$, let $\map P n$ be the proposition:
:$F_n \le \phi^{n - 1}$
=== Basis for the Induction ===
$\map P 1$ is true, as this just says:
:$F_1 = 1 = \phi^0 = \phi^{1 - 1}$
It is also necessary to demonstrate $\map P 2$ is true:
:$F_2 = 1 \le \dfrac {1 + \sqrt 5} 2 = \phi = \phi^{2 - 1}$
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P k$ is true, for all $1 \le k \le n$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:$F_k \le \phi^{k - 1}$
from which it is to be shown that:
:$F_{k + 1} \le \phi^k$
=== Induction Step ===
This is the induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Second Principle of Mathematical Induction.
Therefore:
:$\forall n \in \N_{> 0}: F_n \le \phi^{n - 1}$
== Also see ==
* Fibonacci Number greater than Golden Section to Power less Two
== Sources ==
* : $\S 1.2.1$: Mathematical Induction: $(3)$
Category:Fibonacci Numbers
Category:Golden Mean
Fibonacci Number n+1 Minus Golden Mean by Fibonacci Number n

== Theorem ==
:$F_{n + 1} - \phi F_n = \hat \phi^n$
where:
:$F_n$ denotes the $n$th Fibonacci number
:$\phi$ denotes the golden mean.
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $28$
Category:Fibonacci Numbers
Category:Golden Mean
Category:Fibonacci Number n+1 Minus Golden Mean by Fibonacci Number n
Fibonacci Number n+1 Minus Golden Mean by Fibonacci Number n/Proof 2

== Theorem ==
== Proof ==
Thus from Recurrence Relation where n+1th Term is A by nth term + B to the n we have:
:$F_{n + 1} = \phi F_n + \hat \phi^n$
whence the result.
Category:Fibonacci Number n+1 Minus Golden Mean by Fibonacci Number n
Fibonacci Number of Even Index by Golden Mean Modulo 1

== Theorem ==
Let $n \in \Z$ be an integer.
Then:
:$F_{2 n} \phi \bmod 1 = 1 - \phi^{-2 n}$
:$F_n$ denotes the $n$th Fibonacci number
:$\phi$ is the golden mean: $\phi = \dfrac {1 + \sqrt 5} 2$
== Proof ==
From definition of$\bmod 1$, the statement above is equivalent to the statement:
:$F_{2 n} \phi - 1 + \phi^{-2 n}$ is an integer
We have:
which is an integer.
Hence the result.
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $31$
Category:Fibonacci Numbers
Category:Golden Mean
Fibonacci Number of Index 2n as Sum of Squares of Fibonacci Numbers

== Theorem ==
Let $F_n$ denote the $n$th Fibonacci number.
Then:
:$F_{2 n} = {F_{n + 1} }^2 - {F_{n - 1} }^2$
== Proof ==
From Honsberger's Identity:
:$\forall m, n \in \Z_{>0}: F_{m + n} = F_{m - 1} F_n + F_m F_{n + 1}$
Setting $m = n$:
== Sources ==
* : $5$
* : $5$
Category:Fibonacci Numbers
Fibonacci Number of Index 3n as Sum of Cubes of Fibonacci Numbers

== Theorem ==
Let $F_n$ denote the $n$th Fibonacci number.
Then:
:$F_{3 n} = {F_{n + 1} }^3 + {F_n}^3 - {F_{n - 1} }^3$
== Proof ==
From Honsberger's Identity:
:$\forall m, n \in \Z_{>0}: F_{m + n} = F_{m - 1} F_n + F_m F_{n + 1}$
Setting $m = 2 n$:
== Sources ==
* : $5$
* : $5$
Category:Fibonacci Numbers
Fibonacci Number of Odd Index by Golden Mean Modulo 1

== Theorem ==
Let $n \in \Z$ be an integer.
Then:
:$F_{2 n + 1} \phi \bmod 1 = \phi^{-2 n - 1}$
where:
:$F_n$ denotes the $n$th Fibonacci number
:$\phi$ is the golden mean: $\phi = \dfrac {1 + \sqrt 5} 2$
== Proof ==
From definition of$\bmod 1$, the statement above is equivalent to the statement:
:$F_{2 n + 1} \phi - \phi^{-2 n - 1}$ is an integer
We have:
Hence:
which is an integer.
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $31$
Category:Fibonacci Numbers
Category:Golden Mean
Fibonacci Number plus Arbitrary Function in terms of Fibonacci Numbers

== Theorem ==
Let $\map f n$ and $\map g n$ be arbitrary arithmetic functions.
Let $\sequence {a_n}$ be the sequence defined as:
:$a_n = \begin{cases}
0 & : n = 0 \\
1 & : n = 1 \\
a_{n - 1} + a_{n - 2} + \map f {n - 2} & : n > 1
\end{cases}$
Let $\sequence {b_n}$ be the sequence defined as:
:$b_n = \begin{cases}
0 & : n = 0 \\
1 & : n = 1 \\
b_{n - 1} + b_{n - 2} + \map g {n - 2} & : n > 1
\end{cases}$
Let $\sequence {c_n}$ be the sequence defined as:
:$c_n = \begin{cases}
0 & : n = 0 \\
1 & : n = 1 \\
c_{n - 1} + c_{n - 2} + x \map f {n - 2} + y \map g {n - 2} & : n > 1
\end{cases}$
where $x$ and $y$ are arbitrary.
Then $\sequence {c_n}$ can be expressed in Fibonacci numbers as:
:$c_n = x a_n + y b_n + \paren {1 - x - y} F_n$
== Proof ==
=== Lemma ===
Hence also:
:$b_n = F_n + \ds \sum_{k \mathop = 0}^{n - 2} F_{n - k - 1} \map g k$
Thus:
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $15$
Category:Fibonacci Numbers
Category:Fibonacci Number plus Arbitrary Function in terms of Fibonacci Numbers
Fibonacci Number plus Arbitrary Function in terms of Fibonacci Numbers/Lemma

== Lemma for Fibonacci Number plus Arbitrary Function in terms of Fibonacci Numbers ==
Let $\map f n$ be an arbitrary arithmetic function.
Let $\sequence {a_n}$ be the sequence defined as:
:$a_n = \begin{cases}
0 & : n = 0 \\
1 & : n = 1 \\
a_{n - 1} + a_{n - 2} + \map f {n - 2} & : n > 1
\end{cases}$
Then:
:$a_n = F_n + \ds \sum_{k \mathop = 0}^{n - 2} F_{n - k - 1} \map f k$
== Proof ==
Trying out a few values:
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$a_n = F_n + \ds \sum_{k \mathop = 1}^{n - 1} F_{n - k - 1} \map f k$
$\map P 0$ is the case:
Thus $\map P 0$ is seen to hold.
=== Basis for the Induction ===
$\map P 1$ is the case:
Thus $\map P 1$ is seen to hold.
$\map P 2$ is the case:
Thus $\map P 2$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P r$ is true, where $r \ge 1$, then it logically follows that $\map P {r + 1}$ is true.
So this is the induction hypothesis:
:$a_r = F_r + \ds \sum_{k \mathop = 0}^{r - 2} F_{r - k - 1} \map f k$
and:
:$a_{r - 1} = F_{r - 1} + \ds \sum_{k \mathop = 0}^{r - 3} F_{r - k - 2} \map f k$
from which it is to be shown that:
:$a_{r + 1} = F_{r + 1} + \ds \sum_{k \mathop = 0}^{r - 1} F_{r - k} \map f k$
=== Induction Step ===
This is the induction step:
So $\map P r \implies \map P {r + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$a_n = F_n + \ds \sum_{k \mathop = 0}^{n - 2} F_{n - k - 1} \map f k$
Category:Fibonacci Number plus Arbitrary Function in terms of Fibonacci Numbers
Fibonacci Number plus Binomial Coefficient in terms of Fibonacci Numbers

== Theorem ==
Let $m \in \Z_{>0}$ be a positive integer.
Let $\sequence {a_n}$ be the sequence defined as:
:$a_n = \begin{cases} 0 & : n = 0 \\ 1 & : n = 1 \\ a_{n - 2} + a_{n - 1} + \dbinom {n - 2} m & : n > 1 \end{cases}$
where $\dbinom {n - 2} m$ denotes a binonial coefficient.
Then $\sequence {a_n}$ can be expressed in Fibonacci numbers as:
:$a_n = F_{m + 1} F_{n - 1} + \paren {F_{m + 2} + 1} F_n - \ds \sum_{k \mathop = 0}^m \binom {n + m - k} k$
== Proof ==
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$a_n = F_{m + 1} F_{n - 1} + \paren {F_{m + 2} + 1} F_n - \ds \sum_{k \mathop = 0}^m \binom {n + m - k} k$
=== Basis for the Induction ===
$\map P 0$ is the case:
Thus $\map P 0$ is seen to hold.
$\map P 1$ is the case:
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P {k - 1}$ and $\map P k$ are true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:$a_{k - 1} = F_{m + 1} F_{k - 2} + \paren {F_{m + 2} + 1} F_{k - 1} - \ds \sum_{r \mathop = 0}^m \binom {k - 1 + m - r} r$
:$a_k = F_{m + 1} F_{k - 1} + \paren {F_{m + 2} + 1} F_k - \ds \sum_{r \mathop = 0}^m \binom {k + m - r} r$
from which it is to be shown that:
:$a_{k + 1} = F_{m + 1} F_k + \paren {F_{m + 2} + 1} F_{k + 1} - \ds \sum_{r \mathop = 0}^m \binom {k + 1 + m - r} r$
=== Induction Step ===
This is the induction step:
So $\map P {k - 1} \land \map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \Z_{\ge 0}: a_n = F_{n - 1} r + F_n s$
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $14$
Category:Fibonacci Numbers
Category:Binomial Coefficients