\chapter[ Recurrences]{Recurrences}\index{recurrence equation}
The recursive definition of the Fibonacci numbers is well-known: 
if $F_n$ is the $n^{\textrm{th}}$ Fibonacci number then \nevindex{Fibonacci, Leonardo Pisano (1170--1250)}
\[F_0=0, \;\; F_1=1 \koz , \]
\[F_{n+2}=F_{n+1}+ F_n, \quad \textrm{ if } \; n\ge 0 \koz .\]
We are interested in an explicit form of  the numbers $F_n$ for all natural numbers $n$. 
Actually, the problem is to solve an equation where the unknown is given recursively, 
in which case the equation is called a \ki{recurrence equation.} 
The solution can be considered as a function over natural numbers, because 
 $F_n$ is defined for all $n$. Such recurrence equations are also known as 
 \ki{difference equations,} \index{difference equation} but could be named as \ki{discrete differential equations} 
 for their similarities to differential equations. \index{discrete differential equations}
  
\begin{defi}
A \ki{k$^\textrm{th}$th order recurrence equation} $(k\ge 1)$ is an equation of the form 
\begin{equation}
f(x_{n}, x_{n+1}, \ldots, , x_{n+k})=0, \quad  \quad n \geq 0 \koz , \label{KZrekegy}
\end{equation}
where $x_n$ has to be given in an explicit form. 
\end{defi}
For a unique determination of $x_n$, $k$ initial values must be given. 
Usually these values are $x_0, x_1, \ldots, x_{k-1}$. 
These  can be considered as \ki{initial conditions.}\inddef{initial condition}
In case of the equation for Fibonacci-numbers, 
which is of second order, two initial values must be given.

A sequence $x_n = g(n)$ satisfying equation  (\ref{KZrekegy}) and the corresponding 
initial conditions is called a \ki{particular solution.}\inddef{particular solution}  
If all particular solutions of equation (\ref{KZrekegy}) can be obtained 
from the sequence $x_n = h(n,C_1,C_2,\ldots,C_k)$, by adequately 
choosing of the constants $C_1,C_2,\ldots,C_k$, then this sequence $x_n$ is a 
\ki{general solution.}\inddef{general solution} 

Solving recurrence equations is not an easy task. In this chapter we will discuss 
methods which can be used in special cases. For simplicity of writing we will use the notation 
$x_n$ instead of $x(n)$ as it appears in several books (sequences can be considered 
as functions over natural numbers).   

The chapter is divided into three sections. In Section \ref{KZsec:linrek} we deal with solving 
linear recurrence equations, in Section \ref{KZsec:genfugg} with generating functions and 
their use in solving recurrence equations and in Section  \ref{KZsec:nummeg} 
we focus our attention on the numerical solution of  recurrence equations.

\section{Linear recurrence equations\label{KZsec:linrek}}\index{recurrence equation!linear}
If the recurrence equation is of the form
\[f_0(n)x_n +f_1(n)x_{n+1} +\cdots + f_k(n)x_{n+k}= f(n), \quad n\ge 0 \koz ,\]
where $f, f_0, f_1, \ldots, f_k$ are functions defined over natural numbers,  $f_0,f_k \neq 0$, 
and  $x_n$ has to be given explicitly, then  the recurrence equation is \ki{linear.}  
If $f$ is the zero function, then the equation is \ki{homogeneous,} otherwise \ki{nonhomogeneous.}  
If all the functions $f_0, f_1, \ldots, f_k$ are constant, the equation is called 
a  \ki{linear recurrence equation with constant coefficients.} 

\subsection{Linear homogeneous equations with constant coefficients}
\index{recurrence equation!linear homogeneous}
\index{recurrence equation!linear}

Let the equation be
\begin{equation}
a_0x_n +a_1x_{n+1} +\cdots +a_kx_{n+k}= 0, \quad \quad n \geq k \koz , \label{KZegy:homlin}
\end{equation}
where $a_0, a_1, \ldots, a_k $ are real constants, $a_0,a_k\neq 0, \; k\ge 1$. 
 If $k$ initial conditions are given (usually $x_0,x_1,\ldots, x_{k-1}$), 
then the general solution of this equation can be uniquely given.

To solve the equation let us consider its  
\ki{characteristic equation}\inddef{characteristic equation} 
\begin{equation}
a_0 +a_1r +\cdots + a_{k-1}r^{k-1}+ a_kr^k= 0 \koz , \label{KZKZkaregy}
\end{equation}
a polynomial equation with real coefficients. This equation has $k$ roots in the field of complex numbers. It can  easily be seen after a simple substitution that if $r_0$ is a real solution of the characteristic equation,  then
 $C_0r_0^n$ is a solution of (\ref{KZegy:homlin}), for arbitrary $C_0$.

The general solution of equation (\ref{KZegy:homlin}) is 
\[x_n=C_1x_n^{(1)}+C_2x_n^{(2)}+ \cdots + C_kx_n^{(k)} \koz ,\]
where $x_n^{(i)}$ ($i=1,2,\ldots ,k$) are the linearly independent solutions of equation  (\ref{KZegy:homlin}). 
The constants $C_1, C_2, \ldots, C_k$ can be determined from the initial conditions by solving a system of $k$ equations.

The linearly independent solutions are supplied by the roots of the characteristic equation in the following way. 
A \ki{fundamental solution}\inddef{fundamental solution} of equation (\ref{KZegy:homlin}) 
can be associated with each root of the characteristic equation. Let us consider the following cases.

\noindent \textbf{Distinct real roots.}  Let $r_1,r_2,\ldots, r_p$ be distinct real roots 
of the characteristic equation. Then  
\[r_1^n, \;r_2^n,\; \ldots,\; r_p^n\] are solutions of equation (\ref{KZegy:homlin}), and
\begin{equation}
 C_1r_1^n+C_2r_2^n+ \cdots +C_pr_p^n \label{KZkulgyok} 
\end{equation} 
is also a solution, for arbitrary constants $C_1$, $C_2, \ \ldots, \ C_p$. If $p=k$, 
then (\ref{KZkulgyok}) is the general solution of the recurrence equation.

\begin{pelda}\label{KZpelda:Rek1} Solve the  recurrence equation
\[x_{n+2}=x_{n+1}+x_n, \;\; x_0=0, \; x_1=1 \koz .\]
The corresponding characteristic equation is
\[r^2-r-1=0 \koz ,\]  
with the solutions
\[r_1=\frac{1 + \sqrt{5}}{2} \koz , \ \  r_2 = \frac{1 - \sqrt{5}}{2} \koz .\]
These are distinct real solutions, so the general solution of the equation is
\[x_n=C_1\left(\frac{1 + \sqrt{5}}{2}\right)^n+ C_2\left(\frac{1 - \sqrt{5}}{2}\right)^n \koz . \]
The constants  $C_1$ and  $C_2$ can be determined using the initial conditions. From  $ x_0=0$, $x_1=1$ the following system of equations can be obtained.
\begin{eqnarray*}
    C_1+C_2&=&0 \koz ,  \\
    C_1\frac{1 + \sqrt{5}}{2}+ C_2\frac{1 - \sqrt{5}}{2}&=&1 \koz .
\end{eqnarray*}  
The solution of this system of equations is $C_1= 1/\sqrt{5}, \ C_2= - 1/\sqrt{5}$ \koz .
Therefore the general solution is
\[x_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 ,\]
which is  the $n$th Fibonacci number  $F_n$. \nevindex{Fibonacci, Leonardo Pisano (1170--1250)}
\end{pelda}

\noindent \textbf{Multiple real roots.}  
Let  $r$ be a real root of the characteristic equation with multiplicity  $p$. Then    
\[ r^n, \;nr^n, \;n^2r^n, \;\ldots,\; n^{p-1}r^n\]
are solutions of equation (\ref{KZegy:homlin})  (fundamental solutions corresponding to $r$), and
\begin{equation}
\big(C_0+C_1n+C_2n^2+\cdots + C_{p-1}n^{p-1}\big)r^n \label{KZtobbgyok}
\end{equation} 
is also a solution, for any constants $C_0$, $C_1, \ \ldots, \ C_{p-1}$. If the characteristic equation has no other solutions, then (\ref{KZtobbgyok}) is a general solution of the recurrence equation.  

\begin{pelda}\label{KZpelda:Rek2}
  Solve the recurrence equation
\[x_{n+2}= 4x_{n+1}-4x_n ,\;\; x_0=1, \; x_1=3 \koz .\]
 The characteristic equation is
\[ r^2-4r+4=0 \koz ,\]  
with $r=2$ a solution with multiplicity 2. Then   
\[x_n= (C_0+C_1n)2^n\]
is a general solution of the recurrence equation. 

From the initial conditions we have
\begin{eqnarray*}
          C_0&=&1 \koz ,      \\ 
         2C_0+2C_1&=&3 \koz .
\end{eqnarray*}   
From this system  of equations $C_0=1$, $C_1= 1/2$, so the general solution is
\[x_n=\left(1+\frac{1}{2}n\right)2^n \;\;\;\textrm{ or }\;\;\; x_n=(n+2)2^{n-1} \koz .\]
\end{pelda}

\textbf{Distinct complex roots.}  
If the complex number  $a(\cos b+i\sin b)$, written in trigonometric form, is a root of the characteristic equation, then its conjugate $a(\cos b-i\sin b)$ is also a root, because  the coefficients of the characteristic equation are real numbers. Then
\[ a^n\cos bn\;\; \textrm{ and } \;\; a^n\sin bn\] 
 are  solutions of equation  (\ref{KZegy:homlin}) and
\begin{equation}
 C_1a^n\cos bn+ C_2a^n\sin bn \label{KZkomplex1}
\end{equation}
is also a solution, for any constants $C_1$ and $C_2$. If these are the only solutions 
of a second order characteristic equation, then 
 (\ref{KZkomplex1}) is a general solution.    

\begin{pelda}
  Solve the recurrence equation 
\[x_{n+2}= 2x_{n+1}-2x_n ,\;\; x_0=0, \; x_1=1 \koz .\]
 The corresponding characteristic equation is 
\[ r^2-2r+2=0 \koz ,\]
with roots $1+i$ and $1-i$. These can be written in trigonometric form as 
$\sqrt{2}(\cos (\pi/4) + i \sin (\pi/4))$  and  $\sqrt{2}(\cos (\pi/4) - i \sin (\pi/4))$. Therefore 
\[x_n=C_1(\sqrt{2})^n\cos \frac{n\pi}{4}  + C_2 (\sqrt{2})^n \sin \frac{n\pi}{4}  \] is a general solution of the recurrence equation.
From the initial conditions  
   \begin{eqnarray*}
          C_1&=&0 \koz ,      \\ 
         C_1\sqrt{2}\cos \frac{\pi}{4}+ C_2\sqrt{2}\sin \frac{\pi}{4}&=&1 \koz .  
   \end{eqnarray*} Therefore  $C_1=0, \; C_2=1$. Hence the general solution is
\[ x_n=\big(\sqrt{2}\big)^n\sin \frac{n\pi}{4} \koz .\]
\end{pelda}


\textbf{Multiple complex roots.}  
If the complex number written in trigonometric form as $a(\cos b+i\sin b)$ is a root of the characteristic equation with multiplicity $p$, then its conjugate
$a(\cos b-i\sin b)$ is also a root with multiplicity $p$.
 
Then  
\[ a^n\cos bn,\; na^n\cos bn,\;\ldots, \; n^{p-1}a^n\cos bn\] and
\[ a^n\sin bn,\; na^n\sin bn,\;\ldots, \;  n^{p-1}a^n\sin bn\] are solutions of the recurrence equation  (\ref{KZegy:homlin}).  
Then 
\[ (C_0+ C_1n+ \cdots+C_{p-1}n^{p-1})a^n\cos bn +  (D_0+D_1 n+\cdots+D_{p-1}n^{p-1})a^n\sin bn \]
is also a solution, where $C_0,C_1, \ldots, C_{p-1}, D_0, D_1, \ldots , D_{p-1}$ are  arbitrary constants, 
which can be determined from the initial conditions. This solution is general if the characteristic equation has no other roots. 

\begin{pelda}\label{KZpelda:Rek4}
  Solve the recurrence equation  
\[x_{n+4}+ 2x_{n+2}+ x_n =0,\;\; x_0=0, \; x_1=1, \; x_2=2, \; x_3=3 \koz .\]
The characteristic equation is 
\[r^4+2r^2+1=0 \koz ,\]
which can be written as  $(r^2+1)^2=0$. The complex numbers $i$  and  $-i$ are double roots. The trigonometric form of these are
\[i= \cos \frac{\pi}{2}+ i\sin \frac{\pi}{2}, \;\textrm{ and } \;-i= \cos \frac{\pi}{2}- i\sin \frac{\pi}{2} \] respectively.
 Therefore the general solution is 
\[ x_n = (C_0+C_1n) \cos\frac{n\pi}{2}+  (D_0+D_1n) \sin\frac{n\pi}{2}\;. \]
From the initial conditions we obtain
\begin{eqnarray*}
         C_0&=&0 \koz ,      \\ 
         (C_0+C_1)\cos \frac{\pi}{2}+(D_0+D_1)\sin \frac{\pi}{2}&=&1 \koz ,\\
         (C_0+2C_1)\cos\pi + (D_0+2D_1)\sin\pi &=&2 \koz ,    \\
         (C_0+3C_1)\cos\frac{3\pi}{2}+(D_0+3D_1)\sin\frac{3\pi}{2}&=&3 \koz ,   
\end{eqnarray*}
that is
\begin{eqnarray*}
         C_0&=&0 \koz ,      \\ 
         D_0+D_1&=&1 \koz ,\\
         -2C_1&=&2 \koz ,    \\
         -D_0-3D_1&=&3 \koz .   
   \end{eqnarray*}
Solving this system of equations  
$C_0=0$, $C_1=-1$, $D_0= 3$ and  $D_1=-2$. Thus the general solution is 
\[x_n= (3-2n)\sin \frac{n\pi}{2}-n \cos \frac{n\pi}{2}  \koz .\]
\end{pelda}

Using these four cases all linear homogeneous equations with constant coefficients can be solved, if we can solve their characteristic equations.
  
\begin{pelda}
  Solve the recurrence equation
\[x_{n+3}= 4x_{n+2}-6x_{n+1}+4x_n,\;\; x_0=0, \; x_1=1, \; x_2=1 \koz .\]
The characteristic equation is 
\[r^3-4r^2+6r-4=0 \koz ,\]
with roots 2, $1+i$  and  $1-i$. Therefore the general solution is 
\[ x_n = C_1 2^n +C_2 \big(\sqrt{2}\big)^n\cos\frac{n\pi}{4}+ C_3 \big(\sqrt{2}\big)^n\sin\frac{n\pi}{4} \koz . \]
After determining the constants we obtain 
\[ x_n = -2^{n-1} + \frac{\big(\sqrt{2}\big)^n}{2}\left(\cos\frac{n\pi}{4}+ 3 \sin\frac{n\pi}{4}\right) \koz .\]
\end{pelda}

\textbf{The general solution.} 
The characteristic equation of the $k$th order linear homogeneous equation (\ref{KZegy:homlin}) 
has $k$ roots in the field of complex numbers, which are not necessarily  distinct.
Let these roots be the following: \\
\indent $r_1$ real, with multiplicity $p_1$ ($p_1\ge 1$),

$r_2$ real, with multiplicity $p_2$ ($p_2\ge 1$),

\ldots 

$r_t$ real, with multiplicity $p_t$ ($p_t\ge 1$),
 
$s_1=a_1(\cos b_1 +i\sin b_1)$ complex, with multiplicity $q_1$  ($q_1\ge 1$),

$s_2=a_2(\cos b_2 +i\sin b_2)$ complex, with multiplicity $q_2$  ($q_2\ge 1$),

\ldots

$s_m=a_m(\cos b_m +i\sin b_m)$ complex, with multiplicity $q_m$  ($q_m\ge 1$). 

\noindent Since the equation has  $k$ roots, $p_1+p_2+\cdots + p_t + 2(q_1+q_2+\cdots + q_m)=k$.

\noindent In this case the general solution of  equation  (\ref{KZegy:homlin}) is  
\begin{eqnarray}
x_n &=& \sum_{j=1}^{t}{\Big(C_0^{(j)}+C_1^{(j)}n+\cdots + C_{p_j-1}^{(j)}n^{p_j-1}\Big)r_j^n }\nonumber \\
    &+& \sum_{j=1}^{m}{\Big(D_0^{(j)}+D_1^{(j)}n+\cdots + D_{q_j-1}^{(j)}n^{q_j-1}  \Big)a_j^n\cos b_jn }\nonumber\\
    &+& \sum_{j=1}^{m}{\Big(E_0^{(j)}+E_1^{(j)}n+\cdots + E_{q_j-1}^{(j)}n^{q_j-1}  \Big)a_j^n\sin b_jn} \koz ,\label{KZaltmeg}
\end{eqnarray}
where

$C_0^{(j)},\; C_1^{(j)},\;\ldots ,\; C_{p_j-1}^{(j)}, \; j=1,2,\ldots, t \koz ,$

$D_0^{(l)},\;E_0^{(l)},\; D_1^{(l)},\; E_1^{(l)},\;\ldots , 
\; D_{p_l-1}^{(l)},\; E_{p_l-1}^{(l)}, \; l=1,2,\ldots,m$ are constants, 
which can be determined from the initial conditions.

The above statements  can be summarised in the following theorem.

\begin{tetel}\label{KZtetel:homlin} Let $k \geq 1$ be an integer and $a_0, \ a_1, \ \ldots, a_k$ 
real numbers with $a_0, \ a_k \neq 0.$ 
The general solution of the linear recurrence equation  (\ref{KZegy:homlin}) 
can be obtained  as a linear combination  of the terms $n^jr_i^n$,  where 
$r_i$  are the roots of the characteristic equation (\ref{KZKZkaregy}) 
with multiplicity $p_i$  ($0 \leq j < p_i$) and the coefficients of the linear combination 
depend on the initial conditions.
\end{tetel}
The proof of the theorem is left to the Reader (see Exercise \ref{KZhomlinbiz}). 

The algorithm for the general solution is the following.
 
\begin{alg}{Linear-Homogeneous}\inddef{\textsc{Linear-Homogeneous}}
1 \' determine the characteristic equation of the recurrence equation \\
2 \' find all roots of the characteristic equation with their multiplicities \\
3 \' find the general solution  (\ref{KZaltmeg}) based on the roots \\
4 \' determine the constants of  (\ref{KZaltmeg}) using the initial conditions, if these exists.  
\end{alg}
\index{recurrence equation!linear homogeneous}\index{recurrence equation!linear}

\subsection{Linear nonhomogeneous recurrence equations}\index{recurrence equation!linear nonhomogeneous}
\index{recurrence equation!linear}

Consider the linear nonhomogeneous recurrence equation with constant coefficients 
\begin{equation}
a_0x_n +a_1x_{n+1} +\cdots + a_k x_{n+k}= f(n) \koz ,\label{KZeq:nemhomlin}
\end{equation}
where $a_0, a_1, \ldots, a_k $ are real constants, $a_0,a_k\neq 0, \; k\ge 1$, and  $f$ is not the zero function. 

The corresponding linear homogeneous  equation  (\ref{KZegy:homlin}) can be solved using Theorem \ref{KZtetel:homlin}.  If  a particular solution of   equation (\ref{KZeq:nemhomlin}) is known, then  
equation (\ref{KZeq:nemhomlin}) can be solved.

\begin{tetel}\label{KZtetel:nemhomlin} Let $k \geq 1$ be an integer, 
$a_0, \ a_1, \ \ldots, a_k$ real numbers, $a_0, \ a_k \neq 0.$ 
If $x_n^{(1)}$  is a particular solution of the linear nonhomogeneous  equation (\ref{KZeq:nemhomlin}) and 
$x_n^{(0)}$ is a general solution of the linear homogeneous equation  (\ref{KZegy:homlin}), then 
\[x_n=x_n^{(0)}+x_n^{(1)}\] is a general solution of the equation (\ref{KZeq:nemhomlin}).
\end{tetel}
The proof of the theorem is left to the Reader (see  Exercise \ref{KZnemhomlinbiz}). 


\begin{pelda}
  Solve the recurrence equation
\[x_{n+2}+x_{n+1}-2x_n = 2^n, \;\; x_0=0, \; x_1=1 \koz.\]
First we solve the homogeneous equation  
\[x_{n+2}+x_{n+1}-2x_n = 0 \koz ,\] 
and obtain the general solution 
\[x_n^{(0)}= C_1 (-2)^n + C_2 \koz ,\] 
since  the roots of the characteristic equation are $-2$ and  1.
It is easy to see that 
\[x_n=C_1(-2)^n +C_2+ 2^{n-2} \koz  \] is a solution of the nonhomogeneous equation. Therefore the general solution is
\[x_n=-\frac{1}{4} (-2)^n+2^{n-2} \quad \textrm{or} \quad x_n=\frac{2^n-(-2)^n}{4} \koz ,\]
The constants  $C_1$ and $C_2$ can be determined using the initial conditions. Thus, 
\[
x_n=\left\{
\begin{array}{ll}
     0,       &\textrm{ if} \; n \textrm{ is even} \koz , \\
     2^{n-1}, &\textrm{ if} \; n \textrm{ is odd} \koz .
\end{array}
 \right.\]
\end{pelda}

A particular solution can be obtained using the 
\textit{method of variation of constants.}\index{method of variation of constants} 
However, there are cases when there is an easier way  of finding  a particular solution. 
In Figure \ref{KZ7.alak} we can see types of functions $f(n)$, 
for which a particular solution $x_n^{(1)}$ can be obtained in the given form 
in the table. The constants can be obtained by substitutions.

\begin{figure}
\begin{center}
\begin{tabular}{|l|l|}\hline
& \\
$ f(n)$   & $ x_n^{(1)}$\\
& \\ \hline\hline
   & \\
 $n^pa^n$ & $(C_0+C_1n+\cdots + C_pn^p)a^n$\\ 
 & \\ \hline
 & \\
 $a^nn^p\sin bn$  & $(C_0+C_1n+\cdots + C_pn^p)a^n\sin bn+(D_0+D_1n+\cdots + D_pn^p)a^n\cos bn  $\\ 
 & \\ \hline
 & \\
 $a^nn^p\cos bn$  & $(C_0+C_1n+\cdots + C_pn^p)a^n\sin bn +(D_0+D_1n+\cdots + D_pn^p)a^n\cos bn $\\ 
 & \\
 \hline
\end{tabular}\caption{The form of particular solutions.}\label{KZ7.alak}
\end{center}
\end{figure}

In the previous example $f(n)=2^n$, so the first case can be used with $a=2$ and $p=0$. 
Therefore we try to find a particular solution of the form $C_02^n$. After substitution we obtain 
$C_0=1/4$, thus the particular solution is \[x_n^{(1)}=2^{n-2} \koz .\]

\begin{gyak}
\ujgyak{Solve the recurrence equation 
\[H_n=2H_{n-1}+1, \; \textrm{ if } n\ge 1, \textrm{ and } \quad H_0=0 \koz . \] 
(Here $H_n$ is the optimal number of moves in the problem of the Towers of Hanoi.\gyakindex{Towers of Hanoi})}
\ujgyakmeg{The characteristic equation of the homogeneous equation \[H_n-2H_{n-1}=0\] is
 \[r-2=0 \koz ,\] thus the general solution using the theorem  \ref{KZtetel:homlin} is $H_n^{(0)}=C_1 2^n.$  
 The right-hand term of the nonhomogeneous equation is 1, thus a particular solution is of the form $C_2$. 
 After substitution  we get $C_2=-1$, thus  $H_n^{(1)}=-1$.

The general solution is of the form $H_n=C_1 2^n - 1$. But $H_0=0$, $C_1=1$, thus   
  $H_n = 2^n - 1$.}
\ujgyak{Analyse the problem of the Towers of Hanoi if $n$ discs have to  be moved from  stick
$A$ to stick $C$ in such a way  that no disc can be moved \textit{directly} from $A$ to $C$ and vice versa. 

\textit{Hint.} Show that if the optimal number of moves is denoted by  $M_n$, and  $n \geq 1,$ 
then $M_n = 3M_{n - 1} + 2.$}
\ujgyakmeg{A disc can be moved in the final right position  only by use of $B$, 
so $M_1 \geq 2.$ For two discs two moves are sufficient, so $M_1 = 2.$ 

If the number of discs is $n + 1$, then we can move the largest disc only if 
$n$ discs were moved to stick $C$ using $M_n$ moves. The largest disc can be put on 
$B$ by only one move, then with $M_n$ new moves all $n$ discs will be moved from $C$ on $A$. 
After this at least one move is needed to put the largest disc on $C$ and  $M_n$ 
moves for the other discs to be moved on $C$.  Then we get 
$M_{n + 1} = 3M_n + 2,$ ha $n \geq 1.$

The corresponding characteristic equation of the homogeneous equation is $r - 3 = 0,$ with the solution 
$M_n^{(0)} = C_1 3^{n - 1}.$ The particular solution of the nonhomogeneous equation, 
using Figure \ref{KZ7.alak}, is $M_n^{(1)} = C_2.$ After substitution we get $C_2 = -1,$ 
so the general solution is $M_n = C_1 3^{n - 1} - 1.$ 
Using the initial condition  $M_1 = 2$ the solution of the problem is $M_n = 3^{n - 1} - 1.$}  
\ujgyak{Solve the  recurrence equation
\[(n+1)R_n=2(2n-1)R_{n-1},\; \textrm{ if } n\ge 1,   \textrm{ and } \quad R_0=1 \koz .\]}
\ujgyakmeg{The presented  method cannot be used because the equation is not with constant coefficients.  
If we write this in the form 
\[C_n=\frac{2(2n-1)}{n+1}C_{n-1}\] and substitute $C_{n-1}$, step  by step we can obtain
\[C_n=\frac{2^n(2n-1)(2n-3)\ldots 1}{(n+1)n\ldots 2}=\frac{2^n(2n)!}{2^n(n+1)!n!} = \frac{1}{n+1}\binom{2n}{n} \koz .\]}
\vspace{-4mm}
\ujgyak{Solve the linear nonhomogeneous recurrence  equation 
\[x_n=2^n-2+ 2x_{n-1}, \; \textrm{ if } n\ge2, \quad \textrm{ and } \quad x_1=0 \koz .\] 
\emph{Hint.} Try to find a particular solution of the form $C_1n2^n+C_2$.} 
\ujgyakmeg{The general solution of the homogeneous equation is $x_n^{(0)}=C_12^n$. 
We try to find a particular solution of the nonhomogeneous equation of the form
$x_n^{(1)}=C_2n2^n+C_3$. After substitution we get $2-C_3=(1-C_2)2^n$, 
which is true for all $n$ if  $x_n^{(1)}=C_2n2^n+C_3$ is a root. 
So $C_2=1$ és $C_3=2$. The general solution is $x_n=C_12^n+n2^n+2,$ and using $x_1=0$ we get 
 $x_n=(n-2)2^n+2.$}
\hardgyak\label{KZhomlinbiz}
Prove Theorem  \ref{KZtetel:homlin}.
\ujgyak\label{KZnemhomlinbiz}
Prove Theorem \ref{KZtetel:nemhomlin}.
\end{gyak}

\section{Generating functions and recurrence equations\label{KZsec:genfugg}}\index{generating function}
Generating functions can be used, among others, to solve recurrence equations, 
count objects (e.g. binary trees), prove identities and solve partition problems.
Counting the number of objects can be done by stating and solving recurrence equations. 
These equations are usually  not linear, and generating functions can help us in solving them.

\subsection{Definition and operations}
Associate a series with the infinite sequence  $(a_n)_{n\ge 0} = \langle  
a_0, a_1, a_2, \ldots , a_n, \ldots \rangle$ the following way 
\[
A(z)=a_0+a_1z+a_2z^2 +\cdots + a_nz^n+ \cdots = \sum_{n\ge 0}{a_nz^n} \koz .
\]
This is called the \ki{generating function} of the sequence $(a_n)_{n\ge 0}$. 
\index{generating function}

For example, in case of the Fibonacci numbers \nevindex{Fibonacci, Leonardo Pisano (1170--1250)}  
\index{Fibonacci number} this generating function is
\[
F(z)= \sum_{n\ge 0}{F_nz^n}= z + z^2+2z^3+ 3z^4+5z^5+8z^6+13z^7+ \cdots \koz . \]
Multiplying  both sides of the equation by  $z$, then  by $z^2$, we obtain
\begin{eqnarray}
  F(z)  & = & F_0 + F_1z + F_2z^2 + F_3z^3+\cdots + F_nz^n \hspace{1mm} +\cdots \koz , \nonumber\\
  zF(z) & = &  \hspace{8mm} F_0z + F_1z^2 + F_2z^3+ \cdots + F_{n-1}z^n+\cdots \koz ,\nonumber\\
  z^2F(z)& =&  \hspace{17mm}              F_0z^2 + F_1z^3+\cdots + F_{n-2}z^n+\cdots \koz .\nonumber
\end{eqnarray}
If we subtract the second and the third equations from the first one term by term, then use  the defining formula of  the Fibonacci numbers, we get
\nevindex{Fibonacci, Leonardo Pisano (1170--1250)}
\[ F(z)(1-z-z^2)= z \koz , \]
that is 
\begin{equation} 
F(z)=  \frac{z}{1-z-z^2} \ . \label{KZFib2002} 
\end{equation}
The correctness of these operations can be proved mathematically, but here we do not want to go into details.
The formulae obtained using  generating functions can usually also be proved using other methods.
 
Let us consider the following generating functions 
\[A(z)=\displaystyle\sum_{n\ge 0}{a_nz^n} \textrm{ and }
B(z)=\displaystyle\sum_{n\ge 0}{b_nz^n}.\] 

The generating  functions $A(z)$ and $B(z)$ are  \textit{equal,} 
if and only if  $a_n=b_n$ for all $n$ natural numbers.
\index{generating functions!operations}

Now we define the following operations with the generating functions:  
addition, multiplication by real number, shift, multiplication, derivation and integration.

\textbf{Addition and multiplication by real number.} 
\[
\alpha A (z)+ \beta B(z) = \sum_{n \ge 0}{(\alpha a_n+\beta b_n) z^n} \koz .
\]

\textbf{Shift.} The generating function 
\[
z^kA(z)= \sum_{n\ge 0}{a_nz^{n+k}}= \sum_{n\ge k}{a_{n-k}z^n}
\] 
represents the sequence  $\;<\underbrace{0,0,\ldots , 0}_k, a_0, a_1, \ldots >\;$, while the generating function
\[
 \frac{1}{z^k} (A(z)- a_0-a_1z-a_2z^2 - \cdots - a_{k-1}z^{k-1})
= \sum_{n \ge k}{a_nz^{n-k}}= \sum_{n\ge 0}{a_{k+n}z^n}
\] represents the sequence $\;<a_k, a_{k+1}, a_{k+2}, \ldots >\;$.

\begin{pelda}
  Let $A(z)=1+z+z^2 + \cdots $. Then
\[
\frac{1}{z}\Big(A(z)-1\Big) = A(z) \;\;\;\; \textrm{ and } \;\;\;\;
	A(z)=\frac{1}{1-z} \koz .
\]
\end{pelda}

\textbf{Multiplication.}
If $A(z)$ and $B(z)$ are generating functions, then        
\begin{eqnarray*}
 A(z)B(z) &=& (a_0+a_1z+\cdots +a_nz^n+ \cdots)(b_0+b_1z+\cdots + b_nz^n+\cdots) \\
          &=&  a_0b_0 + (a_0b_1+a_1b_0)z + (a_0b_2+a_1b_1+ a_2b_0)z^2  +\cdots \\ 
          &=& \sum_{n\ge 0}{s_nz^n}, 
\end{eqnarray*} 
where $\displaystyle{ s_n= \sum_{k=0}^{n}{a_kb_{n-k}}}.$

\medskip
{\em Special case.} If $b_n=1$ for all natural numbers $n$, then 
\begin{equation}
  A(z)\frac{1}{1-z}= \sum_{n\ge 0}{ \left ( \sum_{k=0}^{n}{a_k} \right )z^n } \koz . 
\end{equation}
If, in addition,  $a_n=1$ for all $n$, then
\begin{equation}
  \frac{1}{(1-z)^2}= \sum_{n\ge 0}{(n+1)z^n} \koz .\label{KZexdif}
\end{equation}

\textbf{Derivation.} 

\[
 A'(z)= a_1+2a_2z + 3a_3z^2 + \cdots = \sum_{n\ge 0}{(n+1)a_{n+1}z^n} \koz .
\]

\begin{pelda}
 After differentiating both sides of the generating function
\[ A(z)= \sum_{n\ge 0}{z^n}=\frac{1}{1-z},  
\] 
we obtain 
\[  A'(z)=\sum_{n\ge 1} nz^{n-1} =\frac{1}{(1-z)^2} \koz .
\]
\end{pelda}

\textbf{Integration.} 
\[ \int_{0}^{z}{A(t)dt}= a_0z+ \frac{1}{2}a_1z^2 +\frac{1}{3}a_2z^3 + \cdots =
 \sum_{n\ge 1}{\frac{1}{n}a_{n-1}z^n } \koz . 
 \]

\begin{pelda}
 Let \[ \frac{1}{1-z}=1+z+z^2+z^3+\cdots \koz \]
After integrating  both sides we get
\[ \ln \frac{1}{1-z}= z+ \frac{1}{2}z^2+\frac{1}{3}z^3+ \cdots =
\sum_{n\ge 1}{\frac{1}{n}z^n} \koz .  \]
Multiplying the above generating functions we  obtain  
\[ \frac{1}{1-z}\ln \frac{1}{1-z}= \sum_{n\ge 1}{H_nz^n} \koz , \]
where $\displaystyle{H_n= 1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n} \;\;\;\;
(H_0=0, \;\;H_1=1) }$ are the so-called  \emph{harmonic numbers}. \index{harmonic numbers}
\end{pelda}

\textbf{Changing the arguments.} 
Let 
$A(z)= \sum_{n\ge 0}{a_nz^n}$ represent the sequence 
$\langle a_0,a_1,a_2, \ldots \rangle$, then  
 $A(cz)= \sum_{n\ge 0}{c^na_nz^n}$ represents 
the sequence   $\langle a_0,ca_1,c^2a_2, \ldots c^na_n, \ldots \rangle$. The following statements holds
\[
\frac{1}{2}\Big( A(z)+A(-z) \Big) = a_0+a_2z^2+ \cdots + 
a_{2n}z^{2n}+\cdots \koz ,
\]
\[
\frac{1}{2}\Big( A(z)-A(-z) \Big) = a_1z+a_3z^3+ \cdots + 
a_{2n-1}z^{2n-1}+\cdots \koz .
\]

\begin{pelda}
 Let  $A(z)=1+z+z^2+z^3+\cdots =\displaystyle\frac{1}{1-z}\;.$ 
Then
\[
1+z^2+z^4 +\cdots = \frac{1}{2}\big( A(z)+A(-z) \big)= 
\frac{1}{2}\left(\frac{1}{1-z} +\frac{1}{1+z}\right)= \frac{1}{1-z^2} \koz ,
\] which can also be obtained by substituting $z$ by $z^2$ in  $A(z)$.
 We can obtain the sum of the odd power terms in the same way,
\[  z+z^3+z^5+\cdots = \frac{1}{2}\big( A(z)-A(-z)\big)= 
\frac{1}{2}\left(\frac{1}{1-z}-\frac{1}{1+z}\right)=\frac{z}{1-z^2} \koz . 
\]
\end{pelda}

Using generating functions we can obtain interesting formulae. 
For example, let $A(z) = 1/(1-z) = 1+z+z^2+z^3+\cdots $. Then
$zA\big(z(1+z)\big)= F(z)$, which is  the generating function of the Fibonacci numbers. \nevindex{Fibonacci, Leonardo Pisano (1170--1250)} From this
\[
zA\big(z(1+z)\big)= z+z^2(1+z) + z^3(1+z)^2 + z^4(1+z)^3 +\cdots \koz . 
\] The coefficient of $z^{n+1}$ on the left-hand side is  $F_{n+1}$, that is the 
$(n+1)$th Fibonacci number, \nevindex{Fibonacci, Leonardo Pisano (1170--1250)} while  the coefficient of $z^{n+1}$ on the right-hand side  is
\[\sum_{k\ge 0}{ \binom{n-k}{k}} \koz , \] after using the binomial formula in each term. Hence
\begin{equation}
F_{n+1}= \sum_{k \ge 0}{\binom{n-k}{k}} = \sum_{k=0}^{\lfloor 
  \frac{n+1}{2}\rfloor }{ \binom{n-k}{k}} \koz . \label{KZexfib}
\end{equation}

Remember that the binomial formula can be generalised for all real $r$, 
namely 
\[ (1+z)^r= \sum_{n\ge 0}{\binom{r}{n} z^n} \koz ,\]
which is the generating function of the binomial coefficients for a given $r$.
Here $\displaystyle\binom{r}{n}$ is  a generalisation of the number of 
combinations for any real number $r$, that is 
\[
 \binom{r}{n} = \left\{ 
\begin{array}{ll}
    \displaystyle{\frac{r(r-1)(r-2)\ldots (r-n+1)}{n(n-1) \ldots 1}}, 
                          & \textrm{ if } n> 0 \koz ,\\
    1,  & \textrm{ fi } n=0 \koz ,  \\
    0,  & \textrm{ if }  n <0 \koz .
\end{array}
 \right. 
 \]
We can obtain useful formulae using this generalisation for negative $r$. \index{binomial formula!generalisation of the}
Let 
\[ \frac{1}{(1-z)^m}=(1-z)^{-m}=\sum_{k\ge 0}{ \binom{-m}{k}(-z)^k} \koz .
\]
Since, by a simple computation, we get 
\[ \binom{-m}{k}=(-1)^k \binom{m+k-1}{k} \koz ,
\] 
the following formula can be obtained
\[
  \frac{1}{(1-z)^{m+1}}= \sum_{k\ge 0}{\binom{m+k}{k}z^k} \koz .
\]
Then
\[
 \frac{z^m}{(1-z)^{m+1}}=\sum_{k\ge 0}{\binom{m+k}{k}z^{m+k}}=
\sum_{k\ge 0}{\binom{m+k}{m }z^{m+k}}=\sum_{k\ge 0}{ \binom{k}{m}z^k } \koz ,
\]
and  
\begin{equation}
 \sum_{k\ge 0}{\binom{k}{m}z^k} =\frac{z^m}{(1-z)^{m+1}} \koz ,  \label{KZkm}
\end{equation}
where  $m$ is a natural number.  

\subsection{Solving recurrence equations by generating functions}
\index{recurrence equation!solving with generating functions}\label{KZ7.2.2}

If the generating function of the general solution of a recurrence equation to be solved can be 
expanded in such a way that the  coefficients are in closed form, then this method is successful.
 
Let the recurrence equation be
\begin{equation}
F(x_n, x_{n-1}, \ldots, x_{n-k})=0 \koz . \label{KZrekur}
\end{equation}
To solve it, let us consider the generating function 
\[X(z)=\displaystyle\sum_{n\ge 0}{x_nz^n}.\]  If (\ref{KZrekur})
can be written as  $G\big(X(z)\big)=0$ and  can be solved for $X(z)$, 
then $X(z)$ can be expanded into series in such a way that  $x_n$ can be written in closed form, 
 equation (\ref{KZrekur}) can be solved. 

Now we give a general method for solving linear nonhomogeneous recurrence equations. After this we give  three examples for the nonlinear case. In the first two examples the number of elements in some sets of binary trees, while in the third example the number of leaves of binary trees is computed.  
The corresponding recurrence equations (\ref{KZbin1}), (\ref{KZfrunza}) and (\ref{KZreknk})
will be solved using generating functions.

\subsubsection{Linear nonhomogeneous recurrence equations with constant coefficients.}\index{recurrence equation!linear} 
Multiply both sides of equation  (\ref{KZeq:nemhomlin}) by  $z^n$. Then
\[
a_0x_nz^n +a_1x_{n+1}z^n +\cdots +a_kx_{n+k}z^n= f(n)z^n \koz .
\]
Summing up both sides of the equation term by term  we get
\[
a_0\sum_{n\ge 0}{x_nz^n} +a_1\sum_{n\ge 0}{x_{n+1}z^n} +\cdots +a_k\sum_{n\ge 0}{x_{n+k}z^n}= \sum_{n\ge 0}{f(n)z^n} \koz .
\] Then
\[
a_0\sum_{n\ge 0}{x_nz^n} +\frac{a_1}{z}\sum_{n\ge 0}{x_{n+1}z^{n+1}} +\cdots +
\frac{a_k}{z^k}\sum_{n\ge 0}{x_{n+k}z^{n+k}}= \sum_{n\ge 0}{f(n)z^n} \koz .
\] Let 
\[X(z)= \sum_{n\ge 0}{x_nz^n} \quad \textrm{and} \quad  F(z)= \sum_{n\ge 0}{f(n)z^n} \koz .\]
The equation can be written as
\[
a_0X(z)+ \frac{a_1}{z}\Big(X(z)-x_0\Big)+\cdots +\frac{a_k}{z^k}\Big(X(z)-x_0-x_1z- \cdots - x_{k-1}z^{k-1} \Big)=F(z) \koz .
\] This can be solved for $X(z)$. If  $X(z)$ is a rational fraction, then it can be decomposed into partial (elementary) fractions which, after expanding them into series, will give us the general solution  $x_n$ of the original recurrence equation.  We can also try to use the expansion into series  in  the case when the function is not a rational fraction.

\begin{pelda}
Solve the following equation using the above method
\[ x_{n+1}-2x_{n}=2^{n+1}-2, \textrm{ if } n\ge 0 \quad \textrm{ and } x_0=0 \koz .
\]
After multiplying and summing we have
\[
   \frac{1}{z}\sum_{n\ge 0}{x_{n+1}z^{n+1}} -2\sum_{n\ge 0}{x_{n}z^n}=2\sum_{n\ge 0}{2^nz^n}-2\sum_{n\ge 0}{z^n} \koz ,
\] and 
\[
   \frac{1}{z}\Big( X(z)-x_0 \Big) -2X(z)=\frac{2}{1-2z}-\frac{2}{1-z} \koz .
\]  Since  $x_0=0$, after decomposing the right-hand side into partial 
fractions\footnote{ For decomposing the fraction into partial fractions we can use the Method of   
Undetermined Coefficients.}), the solution of the equation is 
\[
X(z)=\frac{2z}{(1-2z)^2}+\frac{2}{1-z}-\frac{2}{1-2z} \koz .
\]
After differentiating the generating function \[ \frac{1}{1-2z}=\sum_{n\ge 0}{2^nz^n } \] term by term we get
\[\frac{2}{(1-2z)^2}=\sum_{n\ge 1}{n2^nz^{n-1} } \koz .  \]
Thus
\[  X(z)= \sum_{n\ge 0}{n2^nz^n} + 2\sum_{n\ge 0}{z^n}-2\sum_{n\ge 0}{2^nz^n}= \sum_{n\ge 0}{\Big((n-2)2^n+2\Big)z^n } \koz ,\]
therefore
\[x_n= (n-2)2^n+2 \koz .\]
\end{pelda} 
 
\subsubsection{The number of binary trees.}\index{binary trees!counting} 
\index{generating functions!counting binary trees} 

Let us denote by $b_n$ the number of binary trees with $n$ vertices. 
Then  $b_1=1$, $b_2=2$, $b_3=5$ (see Figure \ref{KZbinarisfak}).
Let $b_0=1$. (We will see later that this is a good choice.)

\epskepnagy{figs/7-1}{Binary trees with two and three vertices.\label{KZbinarisfak}}{width=12cm}

In a binary tree with  $n$ vertices, there are altogether $n-1$ vertices in the left and right subtrees.
If the left subtree has  $k$ vertices and the right subtree has $n-1-k$ vertices, 
then there exists $b_kb_{n-1-k}$ such binary trees. 
Summing over $k=0,1,\ldots, n-1$, we obtain exactly the number $b_n$ of binary trees. 
Thus for any natural number $n\ge 1$ the recurrence equation in $b_n$ is 
\begin{equation}
 b_n = b_0b_{n-1}+ b_1b_{n-2} +\cdots + b_{n-1}b_0 \koz . \label{KZbin1}    
\end{equation}
This can also be written  as 
\[  b_n  =  \sum_{k=0}^{n-1}{b_kb_{n-1-k}} \koz .
\]
Multiplying both sides by  $z^n,$ then summing over all $n$, we obtain 
\begin{equation}
 \sum_{n\ge 1}^{}{b_nz^n} = \sum_{n\ge 1}^{}{
      \left(\sum_{k=0}^{n-1}{b_kb_{n-1-k}} \right)z^n} \koz .   \label{KZbintree}
\end{equation}
Let $B(z)= \displaystyle\sum_{n\ge 0}{b_nz^n}$ be  the generating function of the numbers $b_n$. The left-hand side  of (\ref{KZbintree}) is exactly  $B(z)-1$ (because $b_0=1$). The right-hand side looks like a product of two generating functions. To see which functions are in consideration, let us use the  notation
\[  A(z)= zB(z)= \sum_{n\ge 0}{b_nz^{n+1}}= 
    \sum_{n\ge 1}{b_{n-1}z^n} \koz . 
\]
Then the right-hand side of  (\ref{KZbintree}) is exactly  $A(z)B(z)$, which is  $zB^2(z)$. Therefore
\[ B(z)-1= zB^2(z), \;\;\;\;B(0)=1 \koz . \]
Solving this equation  for  $B(z)$ gives 
\[ B(z)= \frac{1\pm \sqrt{1-4z}}{2z} \koz .\]
We have to choose the negative sign because $B(0)=1.$  Thus
\begin{eqnarray*}
B(z)&=& \frac{1}{2z} \left(  1- \sqrt{1-4z}  \right)= \frac{1}{2z}\left (
 1-(1-4z)^{1/2}  \right)
 \\
&=&  \frac{1}{2z}\left( 1-\sum_{n\ge 0}{\binom{1/2}{n}(-4z)^n } \right)
=\frac{1}{2z}\left( 1-\sum_{n\ge 0}{ \binom{1/2}{n}(-1)^n2^{2n}z^n }
 \right)
\\
&=& \frac{1}{2z} - \binom{1/2}{0}\frac{2^0z^0}{2z}+
    \binom{1/2}{1}\frac{2^2z}{2z}- \cdots 
   -\binom{1/2}{n}(-1)^n\frac{2^{2n}z^n}{2z}+\cdots
\\
&=& \binom{1/2}{1}2- \binom{1/2}{2}2^3z + \cdots - 
  \binom{1/2}{n}(-1)^n2^{2n-1}z^{n-1}+ \cdots 
\\
&=& \sum_{n \ge 0}{ \binom{1/2}{{n+1} } (-1)^n 2^{2n+1}z^n  }=
 \sum_{n\ge 0}{\frac{1}{n+1} \binom{2n}{n} z^n} \koz .
\end{eqnarray*}
Therefore $b_n=\displaystyle{\frac{1}{n+1}\binom{2n}{n }} \koz .$ The numbers $b_n$ are also called the Catalan numbers.

\textit{Remark.}   In the previous computation we used the following formula that can be proved easily
\begin{displaymath}
 \binom{1/2}{n+1}= \frac{(-1)^n}{2^{2n+1}(n+1)}\binom{2n}{n} \koz .
\end{displaymath}


\subsubsection{The number of leaves of all binary trees of \textit{n} vertices.} 

Let us count the number of leaves (vertices with degree 1) in the set of all binary trees of  $n$ vertices.
Denote this number by $f_n$. We remark that the root is not considered leaf even if it is of degree 1.
It is easy to see that $f_2=2$, $f_3=6$. Let   $f_0=0$ and  $f_1=1$, conventionally. 
Later we will see that this choice of the initial values is appropriate. 

As in the case of numbering the binary trees, consider the binary trees of $n$ vertices having $k$ vertices in the  left subtree  and  $n-k-1$ vertices in the right subtree. There are  $b_k$ such left subtrees and  
 $b_{n-1-k}$ right subtrees. If we consider such a left subtree and all such right subtrees, then together
 there are $f_{n-1-k}$ leaves in the right subtrees. So for a given  $k$ there are $b_{n-1-k} f_k+b_k f_{n-1-k}$ leaves. After summing we have 
\[ f_n= \sum_{k=0}^{n-1}{(f_k b_{n-1-k}+b_k f_{n-1-k})} \koz .
\]
By an easy computation we get 
\begin{equation}
f_n= 2(f_0 b_{n-1}+ f_1 b_{n-2}+ \cdots + f_{n-1}b_0),  
     \;\;\; n\ge 2 \koz .
\label{KZfrunza}
\end{equation} This is a recurrence equation, with solution $f_n$.   
Let 
\[
F(z)=\sum_{n\ge 0}{f_nz^n} \;\;\textrm{ and }\;\; B(z)=\sum_{n\ge 0}{b_nz^n} \koz .
\] 
Multiplying both sides of (\ref{KZfrunza}) by  $z^n$ and summing  gives 
\[ 
  \sum_{n\ge 2}{f_nz^n}= 
   2\sum_{n\ge 2}{\left(\sum_{k=0}^{n-1}{f_kb_{n-1-k}}\right)z^n} \koz .
\]
Since $f_0=0$ and $f_1=1$,  
\[  F(z)-z= 2zF(z)B(z) \koz .
\]
Thus 
\[  F(z)= \frac{z}{1-2zB(z)} \koz ,
\]
and since   
\[    B(z)=\frac{1}{2z}\left( 1-\sqrt{1-4z}\; \right) \koz ,
\] we have
\[ 
 F(z)= \frac{z}{\sqrt{1-4z}}=z(1-4z)^{-1/2}=z\sum_{n\ge 0}{{
 \binom{-1/2}{n}}(-4z)^n \koz . }
\]
After the computations
\[ 
  F(z)=\sum_{n \ge 0}{ \binom{2n}{n}z^{n+1} }= 
     \sum_{n\ge 1}{\binom{2n-2}{n-1}z^n } \koz ,
\]
and
\[
   f_n= \binom{2n-2}{n-1}   \quad \textrm{or}\quad
   f_{n+1}= \binom{2n}{n} = (n+1)b_n \koz .
\]


\subsubsection{The number of binary trees with \textit{n} vertices and  \textit{k} leaves.}
A bit harder problem: how many binary trees are there with $n$ vertices and  $k$ leaves?
Let us denote this number by  $b^{(k)}_n$. It is easy to see that   $b^{(k)}_n=0,$ if 
$k>\lfloor (n+1)/2\rfloor$. By a simple reasoning the case $k=1$ can be solved. The result is  
$b^{(1)}_n= 2^{n-1}$ for any natural number $n\ge 1$.
Let  $b^{(0)}_0=1$, conventionally. We will see later that this choice of the initial 
value is appropriate.  
Let us consider, as in case of the previous problems, the left and right subtrees.
If the left subtree has  $i$ vertices and  $j$ leaves, then the right subtree has  $n-i-1$ vertices and  
$k-j$ leaves. The number of these trees is  $b^{(j)}_ib^{(k-j)}_{n-i-1}$. Summing over  $k$ and $j$ gives
\begin{equation}
b^{(k)}_n=2b^{(k)}_{n-1}+\sum_{i=1}^{n-2}{ 
       \sum_{j=1}^{k-1}{b^{(j)}_ib^{(k-j)}_{n-i-1}  } } \koz .\label{KZreknk}
\end{equation}
For solving this recurrence equation the  generating function
    \[B^{(k)}(z)=\displaystyle\sum_{n\ge 0}{b^{(k)}_nz^n}, \quad\textrm{ where } k\ge 1  \] will be used.  
Multiplying both sides of equation  (\ref{KZreknk}) by  $z^n$ and summing over $n=0,1,$  
$2,\ldots $, we get
\[
\sum_{n\ge 1}{b^{(k)}_nz^n}= 2\sum_{n\ge 1}{b^{(k)}_{n-1}z^n}+
    \sum_{n\ge 1}{\left( \sum_{i=1}^{n-2}{ 
         \sum_{j=1}^{k-1}{b^{(j)}_ib^{(k-j)}_{n-i-1}} } \right)z^n \koz . }
\]
Changing the order of summation gives  
\[
\sum_{n\ge 1}{b^{(k)}_nz^n}= 2\sum_{n\ge 1}{b^{(k)}_{n-1}z^n}+
    \sum_{j=1}^{k-1}{\sum_{n\ge 1}{ 
        \left( \sum_{i=1}^{n-2}{b^{(j)}_ib^{(k-j)}_{n-i-1} } \right)} z^n } \koz .
\]
Thus
\[
B^{(k)}(z)= 2zB^{(k)}(z)+ 
      z \left(\sum_{j=1}^{k-1}{ B^{(j)}(z)B^{(k-j)}(z)} \right)
\]
or 
\begin{equation}
 B^{(k)}(z)= \frac{z}{1-2z}
      \left(\sum_{j=1}^{k-1}{ B^{(j)}(z)B^{(k-j)}(z)} \right) \koz .\label{KZbbb}
\end{equation}
Step by step, we can write the following:
\[
B^{(2)}(z)= \frac{z}{1-2z}\Big( B^{(1)}(z)\Big)^2 \koz ,
\] 
\[
B^{(3)}(z)= \frac{2z^2}{(1-2z)^2}\Big( B^{(1)}(z)\Big)^3 \koz  ,
\]
\[
B^{(4)}(z)= \frac{5z^3}{(1-2z)^3}\Big( B^{(1)}(z)\Big)^4 \koz .
\]
Let us try to find the solution in the form
\[
B^{(k)}(z)= \frac{c_kz^{k-1}}{(1-2z)^{k-1}}\Big( B^{(1)}(z)\Big)^k \koz ,
\] where  $c_2=1$, $c_3=2$, $c_4=5$.
Substituting in  (\ref{KZbbb}) gives a recursion for the  numbers  $c_k$ 
\[ c_k= \sum_{i=1}^{k-1}{c_ic_{k-i}} \koz .
\]
We solve this equation using the generating function method.
If  $k=2$, then  $c_2=c_1c_1$, and so $c_1=1$. Let $c_0=1$. 
If  $C(z)= \sum_{n\ge 0}{c_nz^n}$ is the generating function of the numbers  $c_n$, 
then, using the formula of multiplication of the generating functions we obtain
\[
 C(z)-1-z=(C(z)-1)^2 \;\;\;\;\textrm{ or }\;\;\;\; C^2(z)-3C(z)+z+2=0 \koz ,  
\]
thus 
\[
C(z)= \frac{3-\sqrt{1-4z}}{2} \koz.
\]  Since $C(0)=1$, only the negative sign can be chosen.
After expanding the generating function we get 
\begin{eqnarray*}
 C(z)&=& \frac{3}{2}- \frac{1}{2}(1-4z)^{1/2}=
   \frac{3}{2}- \frac{1}{2}\sum_{n\ge 0}{\frac{-1}{2n-1}\binom{2n}{n}z^n}\\
     &=& \frac{3}{2}+\sum_{n\ge 0}{\frac{1}{2(2n-1)}\binom{2n}{n}z^n }=
  1+ \sum_{n\ge 1}{\frac{1}{2(2n-1)}\binom{2n}{n}z^n } \koz .
\end{eqnarray*} 
From this
\[
 c_n=\frac{1}{2(2n-1)}\binom{2n}{n}, \;\; n\ge 1 \koz .
\]
Since $b^{(1)}_n=2^{n-1}$ for $n\ge 1$, it can be proved easily  that  
$B^{(1)} = z/(1-2z).$ Thus 
\[
B^{(k)}(z)= \frac{1}{2(2k-1)}\binom{2k}{k}\frac{z^{2k-1}}{(1-2z)^{2k-1}} \koz .
\]
Using the formula
\[
 \frac{1}{(1-z)^m} = \sum_{n\ge 0}{\binom{n+m-1}{n}z^n } \koz , 
\]
therefore
\begin{eqnarray*}
B^{(k)}(z)&=& \frac{1}{2(2k-1)}\binom{2k}{k}
      \sum_{n\ge 0}{\binom{2k+n-2}{n} 2^n z^{2k+n-1}}
\\
&=&\frac{1}{2(2k-1)}\binom{2k}{k}\sum_{n\ge 2k-1}{ 
      \binom{n-1}{n-2k+1}2^{n-2k+1}z^n} \koz . 
\end{eqnarray*}
Thus
\[
 b^{(k)}_n= \frac{1}{2k-1}\binom{2k}{k}\binom{n-1}{2k-2}2^{n-2k} 
\] or
\[
b^{(k)}_n= \frac{1}{n}\binom{2k}{k}\binom{n}{2k-1}2^{n-2k} \koz . 
\]


\subsection{The Z-transform method}\index{Z-transform method}\index{recurrence equation!linear}
\index{recurrence equation!linear nonhomogeneous}
When solving linear nonhomogeneous  equations using generating functions, 
the solution is usually  done by the expansion of a rational fraction. 
The Z-transform method can help us in expanding such a function.
Let $P(z)/Q(z)$ be a rational fraction, where the degree of $P(z)$ is less, 
than the degree of $Q(z)$. If the roots of the denominator are known, 
the rational fraction can be expanded into  partial fractions 
using the Method of Undetermined Coefficients.

Let us first consider  the case when the denominator has distinct roots  $\alpha_1, \alpha_2,\ldots,  \alpha_k$. 
Then
\[\frac{P(z)}{Q(z)}= \frac{A_1}{z-\alpha_1} +\cdots +  \frac{A_i}{z-\alpha_i}+\cdots +\frac{A_k}{z-\alpha_k} \koz .\]
It is easy to see that 
\[A_i=\lim_{z\rightarrow \alpha_i}(z-\alpha_i)\frac{P(z)}{Q(z)}, \qquad i=1,2, \ldots , k \koz . \]
But
\[\frac{A_i}{z-\alpha_i}= \frac{A_i}{-\alpha_i\left( 1-\displaystyle\frac{1}{\alpha_i}z\right)}= 
\frac{-A_i\beta_i}{1-\beta_iz} \koz , \] 
where $\beta_i= 1/\alpha_i.$ Now, by expanding this partial fraction, we get
\[ \frac{-A_i\beta_i}{1-\beta_iz}= -A_i\beta_i\left(  1+ \beta_i z+ \cdots  + \beta_i^nz^n + \cdots  \right).
\] 
Denote the coefficient of $z^n$ by $C_i(n)$, then $C_i(n)=-A_i\beta_i^{n+1}$, so 
\[C_i(n)= -A_i\beta_i^{n+1}= -\beta_i^{n+1} \lim_{z\rightarrow \alpha_i}(z-\alpha_i)\frac{P(z)}{Q(z)} \koz , \]
or 
\[
C_i(n)= -\beta_i^{n+1}\lim_{z\rightarrow \alpha_i}\frac{(z-\alpha_i)P(z)}{Q(z)} \ . \]
After  the transformation $z\rightarrow 1/z$ and using 
 $\beta_i=1/\alpha_i$ we obtain
 \[C_i(n)=\lim_{z\rightarrow \beta_i}\left ( (z-\beta_i) z^{n-1}\frac{p(z)}{q(z)} \right ) \koz ,
 \] where
 \[\frac{p(z)}{q(z)} = \frac{P(1/z)}{Q(1/z)} \koz . \]
Thus in the expansion of  $X(z)=\displaystyle\frac{P(z)}{Q(z)}$ the coefficient of  $z^n$ is \[C_1(n)+C_2(n)+\cdots + C_k(n) \koz . \]
If  $\alpha$ is a root of the polynomial $Q(z)$, then  $\beta=1/\alpha$ is a root of $q(z)$. 
E.g. if 
\[\frac{P(z)}{Q(z)}= \frac{2z^z}{(1-z)(1-2z)} \koz , 
\;\;\textrm{ then }\;\;\ \frac{p(z)}{q(z)}= \frac{2}{(z-1)(z-2)} \ . \]
If case of multiple roots,  e.g. if $\beta_i$ has multiplicity $p$, their contribution 
to the solution is
\[C_i(n)= \frac{1}{(p-1)!}\lim_{z\rightarrow \beta_i} \frac{d^{p-1}}{dz^{p-1}}
   \left((z-\beta_i)^pz^{n-1} \frac{ p(z)}{q(z)}\right) \koz . \] 
Here $\displaystyle\frac{d^{p}}{dz^{p}}f(z)$  is the  derivative  of order  $p$ of the function $f(z)$.

All these can be summarised in the following algorithm.  
Suppose that the coefficients of the equation are in array $A$, 
and the constants of the solution are in array $C$.
\index{recurrence equation!linear nonhomogeneous}

\begin{alg}{Linear-Nonhomogeneous$(A,k,f)$}\inddef{\textsc{Linear-Nonhomogeneous}}
1 \' let $ a_0x_n +a_1x_{n+1} +\cdots +a_kx_{n+k}= f(n)$ be the equation, where $f(n)$  \\  
\' \qquad is a rational fraction; multiply  both sides by  $z^n$, and sum over all $n$ \\ 
2 \' transform the equation into the form $X(z) = P(z)/Q(z)$, where \\ 
  \' \qquad $X(z) = \sum_{n\ge 0}{x_nz^n},$ $P(z)$ and $Q(z)$ are polynomials \\
3 \' use the transformation  $z\rightarrow 1/z$, and let the result be \\
  \'    \qquad $p(z)/q(z),$ where $p(z)$ are $q(z)$ are polynomials \\
4 \' denote the roots of  $q(z)$ by \\
   \qquad $\beta_1$, with multiplicity $p_1$,  $p_1\ge 1$, \\  
   \qquad $\beta_2$, with multiplicity  $p_2$,  $p_2\ge 1$, \\
   \qquad \ldots \\
   \qquad $\beta_k$, with multiplicity  $p_k$,  $p_k\ge 1$; \\   
   then the  general solution of the original equation is  \\
   $x_n = C_1(n)+C_2(n) +\cdots + C_k(n),$ where \\   
   $C_i(n)= 1/((p_i-1)!)\lim_{z\rightarrow \beta_i} \frac{d^{p_i-1}}{dz^{p_i-1}}
    \left((z-\beta_i)^{p_i}z^{n-1}(p(z)/q(z))\right), i=1,2, \ldots, k.$ \\
5 \' \key{return} $C$
\end{alg}   
   
   If we substitute $z$ by  $1/z$ in the generating function, 
   the result is the so-called Z-transform, for which  similar operations can be 
   defined as for the generating functions. The  residue theorem for the Z-transform 
   gives the same result. The name of the method is derived 
   from this observation.\index{residue theorem} 
 

\begin{pelda} 
Solve the recurrence equation

\[x_{n+1}-2x_n=2^{n+1}-2, \quad \textrm{if} \quad n \ge 0, \quad  x_0 = 0 \koz .\]

\medskip
Multiplying both sides by $z^n$ and summing we obtain
\[ \sum_{n\ge 0}{x_{n+1}z^n}- 2\sum_{n\ge 0}{x_nz^n} = \sum_{n\ge 0}{2^{n+1}z^n} - \sum_{n\ge 0}{2z^n} \koz ,\]
or
\[\frac{1}{z}X(z)-2X(z) = \frac{2}{1-2z}-  \frac{2}{1-z},\quad \textrm{where } X(z)=\sum_{n\ge 0}{x_nz^n} \koz .\]
Thus  
\[X(z)= \frac{ 2z^2}{(1-z)(1-2z)^2} \ . \]
After the transformation  $z\rightarrow 1/z$ we get   
\[\frac{p(z)}{q(z)}= \frac{2z}{(z-1)(z-2)^2} \koz ,\] where the roots of the denominator are 1 with multiplicity 1  and  2 with multiplicity 2.
Thus 
\[C_1=\lim_{z\rightarrow 1}\frac{2z^n}{(z-2)^2}=2 \qquad \textrm{and}\]
\[C_2= \lim_{z\rightarrow 2} \frac{d}{dz}\left(\frac{2z^n}{z-1} \right)= 2\lim_{z\rightarrow 2}
\frac{nz^{n-1}(z-1)-z^n}{(z-1)^2}=2^n(n-2) \koz .\]
Therefore the general solution is 
\[x_n=2^n(n-2)+2, \quad n\ge 0 \koz .\]
\end{pelda}

\vspace{-4mm}
\begin{pelda}
Solve the recurrence equation

\[x_{n+2}=2x_{n+1}-2x_n , \quad \textrm{if} \quad n \ge 0, \quad x_0 = 0, \quad x_1=1 \koz.\]

Multiplying by $z^n$ and summing gives 
\[ \frac{1}{z^2}\sum_{n\ge 0}{x_{n+2}z^{n+2}}= \frac{2}{z}\sum_{n\ge 0}{x_{n+1}z^{n+1}}-
  2\sum_{n\ge 0}{x_nz^n} \koz , \] so
\[ \frac{1}{z^2}\Big( F(z)-z \Big) = \frac{2}{z}F(z)-2F(z) \koz , \]
that is 
\[ F(z)\left( \frac{1}{z^2}-\frac{2}{z}+2 \right)= -\frac{1}{z} \koz . \]
Then  
\[F(1/z)= \frac{-z}{z^2-2z+2} \koz . \] The roots of the denominator are $1+i$ and $1-i$.
Let us compute  $C_1(n)$ and  $C_2(n)$:
\[C_1(n)=\lim_{z\rightarrow 1+i} \frac{-z^{n+1}}{z-(1-i)}=\frac{i(1+i)^n}{2} \; \textrm{ and}\]
\[C_2(n)=\lim_{z\rightarrow 1-i} \frac{-z^{n+1}}{z-(1+i)}=\frac{-i(1-i)^n}{2} \koz . \]
Since
\[1+i= \sqrt{2} \left(\cos \frac{\pi}{4}+i\sin\frac{\pi}{4} \right), \quad  
  1-i= \sqrt{2} \left(\cos \frac{\pi}{4}-i\sin\frac{\pi}{4}\right) \koz ,
\]
raising to the $n$th power gives 
\[(1+i)^n= \big(\sqrt{2}\big)^n \left(\cos \frac{n\pi}{4}+i\sin\frac{n\pi}{4} \right), \quad  
  (1-i)^n= \big(\sqrt{2}\big)^n \left(\cos \frac{n\pi}{4}-i\sin\frac{n\pi}{4}\right) \koz ,
\]
\[x_n=C_1(n)+C_2(n)= \left( \sqrt{2}\right)^n \sin\frac{n\pi}{4} \koz . \]
\vspace{-4mm}
\end{pelda}
\vspace{-8mm}

%\newpage
\vspace{-4mm}
\begin{gyak}
\ujgyak{How many binary trees\gyakindex{binary trees} are there with $n$ vertices and no empty left and right subtrees?}
\ujgyak{How many binary trees are there with  $n$ vertices, in which each vertex which is not a leaf, has exactly two descendants?}
\ujgyak{Solve the following recurrent equation using  generating functions.
\[H_n=2H_{n-1}+1, \quad H_0=0 \koz . \] ($H_n$ is the number of moves in the problem of the Towers of Hanoi.)}
\ujgyak{Solve the following recurrent equation using the Z-transform method.\gyakindex{Z-transform method} 
\[F_{n+2}=F_{n+1}+F_n+1, \textrm{ if } n\ge 0, \; \textrm{ and}\quad F_0=0, F_1=1 \koz .\]}
\vspace{-2mm}
\ujgyak{Solve the following system of recurrence  equations:
\begin{eqnarray*}
       u_n &=& v_{n-1}+u_{n-2} \koz ,\\
       v_n &=& u_n+ u_{n-1} \koz ,
\end{eqnarray*} 
where $u_0=1, u_1=2, v_0=1.$}
\end{gyak}

\vspace{-2mm}
\section{Numerical solution\label{KZsec:nummeg}}
Using the following function we can solve the linear recurrent equations numerically.
The equation is given in the form
\vspace{-1mm}
\[a_0x_n +a_1x_{n+1} +\cdots +a_kx_{n+k}= f(n) \koz , 
\]
\vspace{-1mm}
where $a_0, a_k\not=0, k\ge 1$. The coefficients $a_0,a_1, \ldots, a_k$ are kept in  array $A$, the initial values  $x_0, x_1,\ldots, x_{k-1}$ in array $X$. To find $x_n$ we will compute step by step the values $x_k,x_{k+1}, \ldots, x_n$, keeping in the previous $k$ values of the sequence in the first $k$ positions of $X$  (i.e. in the positions with indices $0,1, \ldots, k-1$).

\begin{algN}{Recurrence$(A,X,k,n,f)$} \inddef{\textsc{Recurrence}}
1 \' \key{for} \= $j\leftarrow k$ \key{to} $n$  \\
2 \'           \> \key{do}   \= $v \leftarrow A[0]\cdot X[0]$\\
3 \'           \>            \> \key{for} \= $i\leftarrow 1 $ \key{to} $k-1$ \\ 
4 \'           \>            \>           \> \key{do} $v\leftarrow v+A[i]\cdot X[i]$\\
5 \'           \>            \> $v\leftarrow\big( f(j-k)-v \big)/A[k]$\\
6 \'           \>            \> \key{if} \= $j\not = n $ \\
7 \'           \>            \>          \> \key{then} \= \key{for} \= $i \leftarrow 0$ \key{to} $k-2$ \\
8 \'           \>            \>          \>             \>       \> \key{do} $X[i]\leftarrow X[i+1]$\\
9 \'           \>            \>          \>             \> $X[k-1]\leftarrow v$ \\
10 \' \key{return} $ v$
\end{algN}

Lines 2--5 compute the values  $x_j$ ($j=k,k+1, \ldots, n$) 
 (using the previous  $k$ values), denoted by $v$ in the algorithm. 
In lines  7--9, if  $n$ is not yet reached, we copy the last $k$ values in the first $k$ positions of   
$X$. In line  10 $x_n$ is obtained.
It is easy to see that the computation time is $\Theta(kn)$, 
if we disregard the time to compute the values of the function.

\begin{gyak}
\ujgyak\label{KZnum1}
How many additions, subtractions, multiplications and divisions are required using the algorithm 
\textsc{Recurrence},\gyakindex{Recurrence@\textsc{recurrence}} while it computes $x_{1000}$  
using the data given in Example \ref{KZpelda:Rek4}?
 %\thechapter.4?
\ujgyakmeg{If we take into account only the operation appearing in the algorithm (omitting the computation 
of the cycle variable and value of the function), then the number of operations are:

\noindent 
$+\;$ \qquad\quad $\;(n-k+1)(k-1)$\\
$-\;$ \qquad\quad $\;n-k+1$\\
$*\;$ \qquad\quad $\;(n-k+1)k$\\
$/\;$ \qquad\quad $\;n-k+1$\\
$\leftarrow$ \qquad\quad $(2n-2k+1)k$

\noindent In the case of $n=1000$, $k=4$, the number of addition is 2991, the number of subtraction  997, the number of multiplications 3988 and the number of divisions 7972.}
\end{gyak}

\vspace{-3mm}
\begin{fld}
\ujfld{Existence of a solution of a homogeneous equation using  generating function}{Prove that 
a linear homogeneous equation  cannot be solved using generating functions\gyakindex{generating function} 
(because $X(z)=0$ is obtained) if and only if   $x_n=0$ for all $n$.}
\ujfldmeg{From the equation  (\ref{KZegy:homlin}), using the method presented in subsection \ref{KZ7.2.2} the following results
\[
a_0X(z)+ \frac{a_1}{z}\Big(X(z)-x_0\Big)+\cdots +\frac{a_k}{z^k}\Big(X(z)-x_0-x_1z- 
\cdots - x_{k-1}z^{k-1} \Big)=0 \koz .
\] After rearranging the terms, we obtain
\[X(z)\left(a_0+\frac{a_1}{z}+\cdots + \frac{a_k}{z^k}\right)=\frac{a_1}{z}x_0+\cdots + \frac{a_k}{z^k}
\big( x_0+x_1z+\cdots + x_{k-1}z^{k-1}\big) \koz .
\] The method cannot be applied only in the case when the right side is zero. 
Multiplying the right side by  $z^k$, we can obtain:
\[
 z^{k-1}(a_1x_0+a_2x_1+\cdots+a_kx_{k-1})+  z^{k-2}(a_2x_0+a_3x_1+\cdots+a_kx_{k-3})\]
\[  +\cdots +
 z^2(a_{k-2}x_0+a_{k-1}x_1+a_kx_2)+ z(a_{k-1}x_0+a_kx_1)+ a_kx_0 \koz . \] The coefficient  $a_k$ never can be equal to zero. The expression can be equal to zero, only when  $x_0=0, x_1=0, \ldots, x_{k-1}=0,$ 
and from this  $x_n=0,$ for all $n,$  results.
}
\ujfld{Complex roots in case of Z-transform}{What happens if  
the roots of the denominator are complex when applying the 
Z-transform method?\felindex{Z-transform method} The solution of the recurrence  equation must be real. Does the method  ensure this? }
\ujfldmeg{The method is applied as in the case of the real numbers. The question is:  
the solution will be real or complex? Because the complex roots always are in pair (one complex number and its conjugate), the  $C_i$s  will be paired too, each complex number having its conjugate, then when we make the summation the imaginary parts will be eliminated, and the solution will be real.}
\end{fld}

\vspace{-3mm}
\begin{fejmegj}
Recurrence equations  are discussed in details by Agarwal\nevindex{Agarwal, Ravi P.} \cite{Agar00}, 
Elaydi \cite{Elaydi95}, Flajolet and Sedgewick \cite{SedgewickFl96}, 
Greene and Knuth \cite{GreeneKn90}, Mickens \cite{Mickens90}, and also in the recent books written 
by Drmota \cite{Drmota2009}, further by Flajolet and Sedgewick \cite{SedgewickFl2009}.
\nevindex{Elaydi, Saber N.}\nevindex{Mickens, Ronald Elbert}\nevindex{Flajolet, 
Philippe}\nevindex{Sedgewick, Robert}\nevindex{Greene, Daniel H.}\nevindex{Agarwal, Ravi P.}
\nevindex{Drmota, Michael}
     
Knuth \cite{Knuth68I} and  Graham, Knuth and Patashnik \cite{GrahamKnPa95} deal with generating functions. 
In the book of Vilenkin  \cite{Vilenkin69} there are a lot of simple and 
interesting problems about recurrences and generating functions.  
\nevindex{Knuth, Donald Ervin}\nevindex{Graham, Ronald Lewis}\nevindex{Patashnik, Oren}\nevindex{Vilenkin, 
Naum Yakovlevich (1920--1992)}  

In \cite{Lovasz99} Lovász\nevindex{Lovász, László} also presents problems on generating functions.\nevindex{Lovász, László}
  
Counting the binary trees  is from Knuth \cite{Knuth68I},\nevindex{Knuth, Donald Ervin} counting the leaves 
in the set of all binary trees and counting the binary trees with 
$n$ vertices and $k$ leaves are from Zoltán Kása \cite{Kasa03}.\nevindex{Kása, Zoltán} 
\end{fejmegj}

