\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\newcommand{\corresp}{\ \longleftrightarrow\ }

\begin{document} 
\inclassproblems{11, Wed.}                    % !! start the paper

%S04 cp13w, soln slightly edited.

\begin{problem}
Define the function $f:\naturals \to \naturals$ recursively by the rules
\begin{align*}
f(0) & = 1,\\
f(1) & = 6,\\
f(n) & = 2f(n-1)+3f(n-2)+4 & \text{ for }n\geq 2.
\end{align*}

\bparts

\ppart Find a closed form for the generating function
\[
G(x) \eqdef f(0) + f(1)x + f(2)x^2 + \cdots + f(n)x^n + \cdots.
\]

\solution{
\[\begin{array}{rclcrcrccr}
         G(x) & = & f(0) & + & f(1)x  & + & f(2)x^2   & + \cdots & + & f(n)x^n  + \cdots\\
       2xG(x) & = &      &   & 2f(0)x & + & 2f(1)x^2  & + \cdots & + & 2f(n-1)x^n + \cdots\\
     3x^2G(x) & = &      &   &        &   & 3f(0)x^2  & + \cdots & + & 3f(n-2)x^n + \cdots\\
4/(1-x) & = & 4    & + & 4x     &   &  4x^2     & + \cdots & + &      4x^n + \cdots
\end{array}\]

Therefore,
\begin{align*}
G(x) & = 2x G(x) + 3x^2 G(x) + \dfrac{4}{1-x} + (f(0)-4) + (f(1)-2f(0)-4)x\\
     & =  2x G(x) + 3x^2 G(x) + \dfrac{4}{1-x} + (1-4) + (6-2-4)x\\
     & =  2x G(x) + 3x^2 G(x) + \dfrac{4}{1-x} - 3.
\end{align*}
It follows that
\[
G(x)(1-2x-3x^2) = \dfrac{4}{1-x} - 3,
\]
and hence
\begin{align}
G(x) & = \frac{\dfrac{4}{1-x} - 3}{(1+x)(1-3x)}\notag\\
     & =  \frac{4}{(1-x)(1+x)(1-3x)} - \frac{3}{(1+x)(1-3x)}\notag\\
     & =  \frac{4- 3(1-x)}{(1-x)(1+x)(1-3x)}\notag\\
     & =  \frac{3x+1}{(1-x)(1+x)(1-3x)}.\label{G1}
\end{align}
}

\ppart Find a closed form for $f(n)$.  \hint Find numbers $a,b,c,d,e,g$ such that
\[
G(x) = \frac{a}{1+dx} + \frac{b}{1+ex} + \frac{c}{1+gx}.
\]


\solution{
From~\eqref{G1} and the method of partial fractions, we conclude that
$d,e,g = -1,1,-3$, respectively.  So we want $a,b,c$ such that
\begin{align}
\dfrac{3x+1}{(1-x)(1+x)(1-3x)}
           & = \dfrac{a}{1-x} + \dfrac{b}{1+x} + \dfrac{c}{1-3x}\label{G2}\\
3x+1 & = a(1+x)(1-3x) + b(1-x)(1-3x) + c(1-x)(1+x).\label{abc}
\end{align}
Setting $x=1$ in~\eqref{abc}, we conclude that $4 = a\cdot 2 \cdot (-2)$,
so
\[
a=-1.
\]
Setting $x=-1$ in~\eqref{abc}, we conclude that $4-3\cdot 2 = b\cdot 2 \cdot 4$, so
\[
b=-\frac{1}{4}.
\]
Setting $x=1/3$ in~\eqref{abc}, we conclude that $4-3(2/3) = c\cdot (2/3)(4/3)$, so
\[
c=\frac{9}{4}.
\]
So from~\eqref{G1} and~\eqref{G2}, we have
\[
G(x) = \frac{-1}{1-x} + \frac{1/4}{1+x} + \frac{9/4}{1-3x}.
\]

Now the coefficient of $x^n$ in $a/(1-x)$ is $a$, the coefficient in
$b/(1+x)$ is $b (-1)^{n}$ and the coefficient in $c/(1-3x)$ is $c 3^{n}$.  For
$n\geq 2$, the coefficient in $G(x)$ is the sum of these coefficients.  So
\[
f(n) = -1 + \frac{(-1)^n}{4} + \frac{9}{4}3^n = \frac{3^{n+2} + (-1)^n}{4} - 1.
\]
}

\eparts
\end{problem}



\section*{Appendix}

\subsection*{Finding a Generating Function for Fibonacci Numbers}
The Fibonacci numbers are defined by:
\begin{align*}
f_0 & \eqdef 0 \\
f_1 & \eqdef 1 \\
f_n & \eqdef f_{n-1} + f_{n-2} \qquad \text{(for $n \geq 2$)}
\end{align*}

Let $F$ be the generating function for the Fibonacci numbers, that is,
\[
F(x) \eqdef f_0 + f_1 x + f_2 x^2 + f_3 x^3 + f_4 x^4 + \cdots
\]
So we need to derive a generating function whose series has coefficients:
\[
\ang{0,\ 1,\ f_1 + f_0,\ f_2 + f_1,\ f_3 + f_2,\ \dots}
\]
Now we observe that
\[
\begin{array}{ccccccccccl}
  & \langle & 0, & 1, & 0, & 0, & 0, & \dots & \rangle
    & \corresp & x \\
  & \langle & 0, & f_0, & f_1, & f_2, & f_3, & \dots & \rangle
    & \corresp & x F(x) \\
+ & \langle & 0, & 0, & f_0, & f_1, & f_2, & \dots & \rangle
    & \corresp & x^2 F(x) \\ \hline
  & \langle & 0, & 1 + f_0, & f_1 + f_0, & f_2 + f_1, & f_3 + f_2, & \dots & \rangle
    & \corresp & x + x F(x) + x^2 F(x) \\
\end{array}
\]
%
This sequence is almost identical to the right sides of the Fibonacci
equations.  The one blemish is that the second term is $1 + f_0$
instead of simply 1.  But since $f_0 = 0$, the second term is ok.

So we have
\begin{align}
F(x) & = x + x F(x) + x^2 F(x). \notag\\
F(x) & = \frac{x}{1 - x - x^2}.\label{Fx}
\end{align}

\subsection*{Finding a Closed Form for the Coefficients}

Now we expand the righthand side of~\eqref{Fx} into partial fractions.
To do this, we first factor the denominator
\[
1 - x - x^2 = (1 - \alpha_1 x) (1 - \alpha_2 x)
\]
where $\alpha_1 = \frac{1}{2}(1 + \sqrt{5})$ and
$\alpha_2 = \frac{1}{2}(1 - \sqrt{5})$ by the quadratic formula.  Next, we
find $A_1$ and $A_2$ which satisfy:
%
\begin{equation}
F(x) = \frac{x}{1 - x - x^2} =
	\frac{A_1}{1 - \alpha_1 x} + \frac{A_2}{1 - \alpha_2 x}\label{pf}
\end{equation}

Now the coefficient of $x^n$ in $F(x)$ will be $A_1$ times the coefficient
of $x^n$ in $1/(1 - \alpha_1 x)$ plus $A_2$ times the coefficient
of $x^n$ in $1/(1 - \alpha_2 x)$.  The coefficients of these fractions
will simply be the terms $\alpha_1^n$ and $\alpha_2^n$ because
\begin{align*}
\frac{1}{1 - \alpha_1 x} & = 1 + \alpha_1 x + \alpha_1^2 x^2 + \cdots \\
\frac{1}{1 - \alpha_2 x} & = 1 + \alpha_2 x + \alpha_2^2 x^2 + \cdots
\end{align*}
by the formula for geometric series.

So we just need to find find $A_1$ and $A_2$. We do this by plugging
values of $x$ into ~\eqref{pf} to generate linear equations in $A_1$ and
$A_2$.  It helps to note that from~\eqref{pf}, we have
\[
x = A_1(1 - \alpha_2 x) +  A_2(1 - \alpha_1 x),
\]
so simple values to use are $x=0$ and $x=1/\alpha_2$.  We can then find
$A_1$ and $A_2$ by solving the linear equations.  This gives:
%
\begin{gather*}
A_1 = \frac{1}{\alpha_1 - \alpha_2} = \frac{1}{\sqrt{5}} \\
A_2 = -A_1 = -\frac{1}{\sqrt{5}}
\end{gather*}
Substituting into~\eqref{pf} gives the partial fractions
expansion of $F(x)$:
%
\[
F(x) =	\frac{1}{\sqrt{5}} \paren{\frac{1}{1 - \alpha_1 x} - \frac{1}{1 - \alpha_2 x}}.
\]
So we conclude that the coefficient, $f_n$, of $x^n$ in the series for $F(x)$ is
\begin{align*}
f_n & = \frac{\alpha_1^n - \alpha_2^n}{\sqrt{5}} \\
                & = \frac{1}{\sqrt{5}}
	\paren{\paren{\frac{1 + \sqrt{5}}{2}}^n -
	\paren{\frac{1 - \sqrt{5}}{2}}^n}
\end{align*}

\end{document}
