\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}

\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{amsthm}
%\usepackage{graphics}
%\usepackage{fullpage}
%\addtolength{\textheight}{2 cm}

\newcommand{\Q}{\mathbb Q}
\newcommand{\Z}{\mathbb Z}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\legendre}[2]{\genfrac(){}{}{#1}{#2}}
\newcommand{\hf}{\hskip -25pt $\bullet$ \hskip 17pt}
\newcommand{\hfa}{\hskip -47pt $\bullet$ \hskip 39pt}
\newcommand{\nehez}{\hskip -30pt ($*$) \hskip 13pt}

\begin{document}

\begin{center}
{\Large \bf Számelmélet 2009/2010 ősz\\
1. gyakorlat: Fibonacci-számok, teljes indukció}
\end{center}

\begin{enumerate}

\item Jelölje az $n$-edik Fibonacci-számot $F_n$, tehát $F_0=0$, $F_1=1$ 
és $n\ge2$-re $F_n=F_{n-1}+F_{n-2}$. Igazoljuk az alábbi összefüggéseket:
\begin{enumerate}
\item $\sum_{i=1}^nF_i=F_{n+2}-1$
\item $\sum_{i=1}^nF_i^2=F_nF_{n+1}$
\item $\left(\frac{1+\sqrt5}2\right)^{n-2}\le F_n<\left(\frac{1+\sqrt5}2\right)^{n-1}$ 
(ha $n\ge2$)
\item $F_{n+k}=F_kF_{n+1}+F_{k-1}F_n$
\item $F_n\mid F_{kn}$
\end{enumerate}

\item
Bizonyítsuk be, hogy minden $n$ természetes számra 
$(1+\sqrt2)^{2n}+(1-\sqrt2)^{2n}$ páros szám, míg
$(1+\sqrt2)^{2n}-(1-\sqrt2)^{2n}$ egy természetes szám  
$\sqrt2$-szerese.

\item
Bizonyítsuk be teljes indukcióval, hogy
\[
F_n=\frac1{\sqrt5}\left(\left(\frac{1+\sqrt5}2\right)^n-
\left(\frac{1-\sqrt5}2\right)^n\right)
\]

\item\hf
Bizonyítsuk be, hogy minden pozitív természetes szám előáll
különböző Fibonacci-számok összegeként. Plusz pontért:
legrosszabb esetben $n$ hány Fibonacci-szám összegeként áll elő?

\item
Mutassuk meg, hogy az 1, 2, 2, 3, 3, 3, 4, 4, 4, 4,\dots sorozat
$n$-edik eleme $\lfloor\sqrt{2n}+\frac{1}{2}\rfloor$.

\item Igazoljuk, hogy minden $n$ pozitív egészre
\begin{enumerate}
\item $7\mid 2^{3n+1}+5$
\item $196\mid 147^n+7^{3n-1}$
\item\hfa $11\mid 5^{n+3}+7^{2n+1}$
\end{enumerate}

\item
Határozzuk meg mindazokat az $n$ természetes számokat, amelyekre
$2^n+1$ osztható 3-mal.

\item\nehez
Bizonyítsuk be, hogy 
\[
F_n=\sum\left\{\binom{\ell}k\,|\,\,0\le k\le\ell \text{ és } \ell+k=n\right\}.
\]


%\item
%Keressük meg azokat az $n$ egész számokat, amelyekre $n-3\mid n^3-3$.

%\item
%Bizonyítsuk be, hogy ha $n$ egész szám, akkor $3n^2+2n+1$ nem osztható 5-tel.



\end{enumerate}
\end{document}
