Fibonacci numbers

[18/67%]

Show

LaTeX

Show LaTeX

Problem 2.14.31 from Кудрявцев Л.Д., Кутасов А.Д., Чехлов В.И., Шабунин М.И. "Интегралы. Ряды." [ККЧ+03]More problems in Subsection 2.14.2 "Problems"

Let $a_{1} = 1, a_{2} = 1, a_{n+1} = a_{n+1}+a_{n}(n \geqslant 1)$ . Prove that the series $\sum_{n = 1}^{\infty } \frac{1}{a_{n}}$ converges.

Problem 8.162 from Pólya G., Szegő G. "Problems and Theorems in Analysis" [PóSz98]More problems in Section 4 "Power Series with Integral Coefficients Associated with Rational Functions"

The sequence of Fibonacci numbers (cf. Problem 53 of Part VII) is periodic mod $m$ , where $m$ is any integer. Calculate the length of the period for all prime numbers less than 30.

Problem 7.53 from Pólya G., Szegő G. "Problems and Theorems in Analysis" [PóSz98]More problems in Section 7.4 "Miscellaneous Problems"

The Fibonacci numbers $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$ are defined as follows: Set $u_{0} = 0$ , $u_{1} = 1$ , $u_{n} + u_{n+1} = u_{n+2}$ for $n = 0, 1, 2, \ldots$ . The linear transformation

y_{n} = \frac{u_{1} x_{1} + u_{2} x_{2} + \cdots + u_{n} x_{n} - u_{n} x_{n+1}}{\sqrt{u_{n} u_{n+2}}}, \qquad n = 1, 2, 3, \ldots

is orthogonal.

Problem 7.10 from Шабунин М.И., Половинкин Е.С., Карлов М.И. "Сборник задач по теории функций комплексного переменного" [ШПК15]More problems in Section 7 "Taylor Series"

Using the method of undetermined coefficients, show that the coefficients $A_{n}$ of the power series

\frac{1}{1-z-z^{2}} = \sum _{n = 0}^{\infty } A_{n} z^{n}

are determined by the conditions $A_{0} = 1, A_{1} = 1, A_{n+1} = A_{n}+A_{n-1}, n \in \mathbb {N}$ . The numbers $A_{n}$ are called the Fibonacci numbers. Prove that

A_{n} = \frac{1}{\sqrt{5}}\left[\left(\frac{\sqrt{5}+1}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right], \quad n \in \mathbb {N}.

Problem 5D.21 from Axler S. "Linear Algebra Done Right" [Axl24]More problems in Section 5D "Diagonalizable Operators"

The Fibonacci sequence $F_{0}, F_{1}, F_{2}, \ldots$ is defined by

F_{0} = 0, F_{1} = 1, \text{ and } F_{n} = F_{n-2}+F_{n-1} \text{ for } n \geq 2

Define $T \in \mathcal{L}\left(\mathbb {R}^{2}\right)$ by $T(x, y) = (y, x+y)$ .

(a)

Show that $T^{n}(0,1) = \left(F_{n}, F_{n+1}\right)$ for each nonnegative integer $n$ .

(b)

Find the eigenvalues of $T$ .

(c)

Find a basis of $\mathbb {R}^{2}$ consisting of eigenvectors of $T$ .

(d)

Use the solution to (c) to compute $T^{n}(0,1)$ . Conclude that

F_{n} = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]

for each nonnegative integer $n$ .

(e)

Use (d) to conclude that if $n$ is a nonnegative integer, then the Fibonacci number $F_{n}$ is the integer that is closest to

\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n}

Remark.

Each $F_{n}$ is a nonnegative integer, even though the right side of the formula in (d) does not look like an integer. The number

\varphi := \frac{1+\sqrt{5}}{2}

is called the golden ratio.

Problem 0.34 from Gallian J.A. "Contemporary Abstract Algebra" [Gal21]More problems in Chapter 0 "Preliminaries"

The Fibonacci numbers are $1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$ . In general, the Fibonacci numbers are defined by $f_1 = 1$ , $f_2 = 1$ , and for $n \geq 3$ , $f_n = f_{n-1} + f_{n-2}$ . Prove that the $n$ th Fibonacci number $f_n$ satisfies $f_n < 2^n$ .

Problem 4.5 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 4 "Recurrence relations. Induction"

Let $u(0)=0, u(1)=1$ , and $u(n)=u(n-1)+u(n-2)$ , where $n \geqslant 2$ . The numbers $u(n)$ are called Fibonacci numbers. Compute $u(n)$ .

Problem 4.11 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 4 "Recurrence relations. Induction"

Let $u(n)$ be the sequence of Fibonacci numbers. Prove that:

(a)

$u(1)+\ldots +u(n)=u(n+2)-1$ ;

(b)

$u(1)^{2}+\ldots +u(n)^{2}=u(n) u(n+1)$ ;

(c)

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

(d)

$u(1)^{3}+\ldots +u(n)^{3}=\frac{1}{10}\left[u(3 n+2)+(-1)^{n+1} 6 u(n-1)+5\right]$ ;

(e)

$u(m+n)=u(m) u(n-1)+u(m+1) u(n)$ ;

(f)

if $n$ divides $m$ , then $u(n)$ divides $u(m)$ ;

(g)

$(u(n), u(m))=u((n, m))$ .

Problem 12.4 from Кострикин А.И. "Сборник задач по алгебре" [Кос15]More problems in Section 12 "Expanding a determinant according to the elements of a row or a column"

Prove that the $(n+1)$ -st term $u(n+1)$ of the sequence of Fibonacci numbers (see 4.5) equals the determinant

\left[\begin{smallmatrix} 1 & 1 & 0 & 0 & \ldots & 0 & 0 \\ -1 & 1 & 1 & 0 & \ldots & 0 & 0 \\ 0 & -1 & 1 & 1 & \ldots & 0 & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & 0 & 0 & \ldots & -1 & 1 \end{smallmatrix}\right]

of order $n$ .

Problem I.3.2.6 from Кострикин А.И. "Основы алгебры" [Кос04]More problems in Section I.3.2 "Further properties of determinants"

Let

C_{n}\left(\lambda _{1}, \ldots , \lambda _{n}\right)=\left\Vert \begin{smallmatrix} \lambda _{1} & 1 & 0 & \ldots & 0 & 0 & 0 \\ -1 & \lambda _{2} & 1 & \ldots & 0 & 0 & 0 \\ \ldots & \ldots \ldots & \ldots \ldots \ldots & \ldots \ldots \ldots \ldots \ldots \ldots \ldots \\ 0 & 0 & 0 & \ldots & \lambda _{n-2} & 1 & 0 \\ 0 & 0 & 0 & \ldots & -1 & \lambda _{n-1} & 1 \\ 0 & 0 & 0 & \ldots & 0 & -1 & \lambda _{n} \end{smallmatrix}\right\Vert .

Show that $\operatorname {det} C_{n}=\lambda_{n} \operatorname {det} C_{n-1}+\operatorname {det} C_{n-2}$ . For $\lambda_{1}=\lambda_{2}=\ldots =\lambda_{n}=1$ , find the numerical value of $\operatorname {det} C_{n}$ .

Problem 1.1.71 from Steeb W., Hardy Y. "Problems and Solutions in Introductory and Advanced Matrix Calculus" [StHa17]More problems in Section 1.1 "Chapter Problems"

The Fibonacci numbers are defined by the recurrence relation (linear difference equation of second order with constant coefficients) $s_{n+2} = s_{n+1}+s_{n}$ , where $n = 0,1,\ldots$ and $s_{0} = 0$ , $s_{1} = 1$ . Write this recurrence relation in matrix form. Find $s_{6}$ , $s_{5}$ , and $s_{4}$ .

Problem 3.2.24 from Steeb W., Hardy Y. "Problems and Solutions in Introductory and Advanced Matrix Calculus" [StHa17]More problems in Section 3.2 "Supplementary Problems"

Let $n \in \mathbb {N}$ . The Fibonacci numbers are provided by the entries of the matrix

\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n}, \qquad n = 1, 2, \ldots .

Find the sequence provided by the $4 \times 4$ matrix

\left(\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \otimes \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\right)^{n}, \qquad n = 1, 2, \ldots .

Compare with the sequence of the Fibonacci numbers. Discuss.

Problem 35 from Дехтярь М.И., Дудаков С.М., Карлов Б.Н., Карлов М.И. "Лекции по дискретной математике" [ДДК+21a]More problems in Chapter 2 "Induction and Combinatorics"

The Fibonacci numbers $F_{i}, i \in \omega$ , are defined as follows: $F_{i}=i$ for $i<2$ , $F_{i}=F_{i-1}+F_{i-2}$ otherwise. Prove that $F_{i}$ is even if and only if $i$ is divisible by 3.

Problem 36 from Дехтярь М.И., Дудаков С.М., Карлов Б.Н., Карлов М.И. "Лекции по дискретной математике" [ДДК+21a]More problems in Chapter 2 "Induction and Combinatorics"

Prove the identity $F_{i-1} F_{i+1}=F_{i}^{2}+(-1)^{i}$ for the Fibonacci numbers, for $i>0$ .

Problem 57 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Задачник по дискретной математике" [ДДК+21b]More problems in Chapter 2 "The Method of Mathematical Induction"

The Fibonacci numbers are defined by the following recurrence relations: $F_{0}=0, F_{1}=1, F_{n+2}=F_{n+1}+F_{n}$ . Prove that

(a)

$F_{n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right] ;$

(b)

$F_{1}+F_{2}+F_{3}+\cdots +F_{n}=F_{n+2}-1$ ;

(c)

$n \cdot F_{1}+(n-1) \cdot F_{2}+(n-2) \cdot F_{3}+\cdots +1 \cdot F_{n}=F_{n+4}-n-3$ for $n \geqslant 1 ;$

(d)

$F_{n-1} F_{n+1}=F_{n}^{2}+(-1)^{n}$ for $n \geqslant 1$ ;

(e)

the numbers $F_{n}$ and $F_{n+1}$ are coprime for $n \geqslant 1$ ;

(f)

the number $F_{n}$ is even if and only if $n$ is divisible by 3;

(g)

$F_{n+m}=F_{n-1} F_{m}+F_{n} F_{m+1}$ for $n \geqslant 1$ .

Problem 58 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Задачник по дискретной математике" [ДДК+21b]More problems in Chapter 2 "The Method of Mathematical Induction"

Prove that for $n \geqslant 1$

\left[\begin{smallmatrix} 1 & 1 \\ 1 & 0 \end{smallmatrix}\right]^{n}=\left[\begin{smallmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{smallmatrix}\right].

Problem 59 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Задачник по дискретной математике" [ДДК+21b]More problems in Chapter 2 "The Method of Mathematical Induction"

Prove that there exist $F_{n+2}$ sequences of zeros and ones of length $n$ in which there are no two consecutive ones.

Problem 91 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Задачник по дискретной математике" [ДДК+21b]More problems in Chapter 3 "Elements of Combinatorics"

Prove the identity $\sum_{2 m \leqslant n+1} C_{n-m+1}^{m}=F_{n+2}$ .

References

[ККЧ+03] Кудрявцев Л.Д., Кутасов А.Д., Чехлов В.И., Шабунин М.И. Интегралы. Ряды. 2-е изд., ФИЗМАТЛИТ, 2003.

[PóSz98] Pólya G., Szegő G. Problems and Theorems in Analysis. Springer, 1998.

[ШПК15] Шабунин М.И., Половинкин Е.С., Карлов М.И. Сборник задач по теории функций комплексного переменного. 4-е изд., БИНОМ. Лаборатория знаний, 2015.

[Axl24] Axler S. Linear Algebra Done Right. 4th ed., Springer, 2024.

[Gal21] Gallian J.A. Contemporary Abstract Algebra. 10th ed., CRC Press, 2021.

[Кос15] Кострикин А.И. Сборник задач по алгебре. МЦНМО, 2015.

[Кос04] Кострикин А.И. Основы алгебры. ФИЗМАТЛИТ, 2004.

[StHa17] Steeb W., Hardy Y. Problems and Solutions in Introductory and Advanced Matrix Calculus. 2nd ed., World Scientific Publishing, 2017.

[ДДК+21a] Дехтярь М.И., Дудаков С.М., Карлов Б.Н., Карлов М.И. Лекции по дискретной математике. 3-е изд., Тверской государственный университет, 2021.

[ДДК+21b] Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. Задачник по дискретной математике. 2-е изд., Тверской государственный университет, 2021.