% Like most advanced LaTeX files, this one begins with a lot of
% boilerplate. You don't need to understand (or even read) most of it.
% All you need to do is fill in your name, UMN ID, email address,
% and the number of the pset. (Search for "METADATA" to find the place
% for this.) Then, you can go straight to the "EXERCISE 1"
% section and start writing your solutions.
% The "VARIOUS USEFUL COMMANDS" section is probably worth taking a
% look at at some point.

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------
\documentclass[paper=a4, fontsize=12pt]{scrartcl} % A4 paper and 12pt font size
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm,amssymb} % Math packages
\usepackage{mathrsfs}    % More math packages
\usepackage{sectsty}  % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape} % Make all section titles centered, the default font and small caps %remove this to left align section tites
\usepackage{hyperref} % Turns cross-references into hyperlinks,
                      % and defines \url and \href commands.
\usepackage{graphicx} % For embedding graphics files.
\usepackage{framed}   % For the "leftbar" environment used below.
\usepackage{ifthen}   % Used for the \powset command below.
\usepackage{lastpage} % for counting the number of pages
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}     % This is a powerful tool to draw vector
                      % graphics inside LaTeX. In particular, you can
                      % use it to draw graphs.
\usepackage{verbatim} % For the "verbatim" environment, in which
                      % special symbols can be used freely without
                      % confusing the compiler. (And it's typeset in
                      % a constant-width font.)
                      % Useful, e.g., for quoting code (or ASCII art).
\usepackage{ytableau}

%\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{20pt} % Makes indentation for paragraphs longer.
                           % This makes paragraphs stand out more.

%----------------------------------------------------------------------------------------
%	VARIOUS USEFUL COMMANDS
%----------------------------------------------------------------------------------------
% The commands below might be convenient. For example, you probably
% prefer to write $\powset[2]{V}$ for the set of $2$-element subsets
% of $V$, rather than writing $\mathcal{P}_2(V)$.
% Notice that you can easily define your own commands like this.
% Caveat: Some of these commands need to be properly "guarded" when
% they occur in subscripts or superscripts. So you should not write
% $K_\CC$, but rather $K_{\CC}$.
\newcommand{\CC}{\mathbb{C}} % complex numbers
\newcommand{\RR}{\mathbb{R}} % real numbers
\newcommand{\QQ}{\mathbb{Q}} % rational numbers
\newcommand{\NN}{\mathbb{N}} % nonnegative integers
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}} % integers modulo k
                                            % (syntax: "\Z{k}")
\newcommand{\ZZ}{\mathbb{Z}} % integers
\newcommand{\id}{\operatorname{id}} % identity map
\newcommand{\lcm}{\operatorname{lcm}}
% Lowest common multiple. For historical reasons, LaTeX has a \gcd
% command built in, but not an \lcm command. The preceding line
% rectifies that.
\newcommand{\rev}{\operatorname{rev}} % reversal of a walk
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
% $\powset[k]{S}$ stands for the set of all $k$-element subsets of
% $S$. The argument $k$ is optional, and if not provided, the result
% is the whole powerset of $S$.
\newcommand{\set}[1]{\left\{ #1 \right\}}
% $\set{...}$ compiles to {...} (set-brackets).
\newcommand{\abs}[1]{\left| #1 \right|}
% $\abs{...}$ compiles to |...| (absolute value, or size of a set).
\newcommand{\tup}[1]{\left( #1 \right)}
% $\tup{...}$ compiles to (...) (parentheses, or tuple-brackets).
\newcommand{\ive}[1]{\left[ #1 \right]}
% $\ive{...}$ compiles to [...] (Iverson bracket, aka truth value).
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
% $\floor{...}$ compiles to |_..._| (floor function).
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
% $\verts{...}$ compiles to V(...) (vertex set of a graph/digraph).
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
% $\edges{...}$ compiles to E(...) (edge set of a graph).
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
% $\arcs{...}$ compiles to A(...) (arc set of a digraph).
\newcommand{\lf}[2]{#1^{\underline{#2}}}
% $\lf{...1}{...2}$ compiles to $...1^{\underline{...2}}$.
% This is a notation for the falling factorial.
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
% $\underbrack{...1}{...2}$ yields
% $\underbrace{...1}_{\substack{...2}}$. This is useful for doing
% local rewriting transformations on mathematical expressions with
% justifications. For example, try this out:
% $ \underbrack{(a+b)^2}{= a^2 + 2ab + b^2 \\ \text{(by the binomial formula)}} $
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
\newcommand{\nnn}{\nonumber\\} % Don't number this line in an "align" environment, and move on to the next line.
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}} % Quotient of division with remainder.

%----------------------------------------------------------------------------------------
%	MAKING SUMMATION SIGNS ALWAYS PUT THEIR BOUNDS ABOVE AND BELOW
%	THE SIGN
%----------------------------------------------------------------------------------------
% The following are hacks to ensure that sums (such as
% $\sum_{k=1}^n k$) always put their bounds (i.e., the $k=1$ and the
% $n$) underneath and above the sign, as opposed to on its right.
% Same for products (\prod), set unions (\bigcup) and set
% intersections (\bigcap). Remove the 8 lines below if you do not want
% this behavior.
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}

%----------------------------------------------------------------------------------------
%	ENVIRONMENTS
%----------------------------------------------------------------------------------------
% The incantations below define how theorem environments
% (\begin{theorem} ... \end{theorem}) and their likes will look like.
\newtheoremstyle{plainsl}% <name>
  {8pt plus 2pt minus 4pt}% <Space above>
  {8pt plus 2pt minus 4pt}% <Space below>
  {\slshape}% <Body font>
  {0pt}% <Indent amount>
  {\bfseries}% <Theorem head font>
  {.}% <Punctuation after theorem head>
  {5pt plus 1pt minus 1pt}% <Space after theorem headi>
  {}% <Theorem head spec (can be left empty, meaning `normal')>

% Environments which make the text inside them slanted:
\theoremstyle{plainsl}
  \newtheorem{theorem}{Theorem}[section]
  \newtheorem{proposition}[theorem]{Proposition}
  \newtheorem{lemma}[theorem]{Lemma}
  \newtheorem{corollary}[theorem]{Corollary}
  \newtheorem{conjecture}[theorem]{Conjecture}
% Environments that don't:
\theoremstyle{definition}
  \newtheorem{definition}[theorem]{Definition}
  \newtheorem{example}[theorem]{Example}
  \newtheorem{exercise}[theorem]{Exercise}
  \newtheorem{examples}[theorem]{Examples}
  \newtheorem{algorithm}[theorem]{Algorithm}
  \newtheorem{question}[theorem]{Question}
 \theoremstyle{remark}
  \newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}

%----------------------------------------------------------------------------------------
%	METADATA
%----------------------------------------------------------------------------------------
\newcommand{\myname}{Darij Grinberg} % ENTER YOUR NAME HERE
\newcommand{\myid}{00000000} % ENTER YOUR UMN ID HERE
\newcommand{\mymail}{dgrinber@umn.edu} % ENTER YOUR EMAIL HERE
\newcommand{\psetnumber}{1} % ENTER THE NUMBER OF THIS PSET HERE

%----------------------------------------------------------------------------------------
%	HEADER AND FOOTER
%----------------------------------------------------------------------------------------
\ihead{Solutions to midterm \#\psetnumber} % Page header left
\ohead{page \thepage\ of \pageref{LastPage}} % Page header right
\ifoot{\myname, \myid} % left footer
\ofoot{\mymail} % right footer

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------
\title{	
\normalfont \normalsize 
\textsc{University of Minnesota, School of Mathematics} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge Math 5705: Enumerative Combinatorics, \\
Fall 2018:
Midterm \psetnumber\\% The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}
\author{\myname}

\begin{document}

\maketitle % Print the title

\begin{center} % Delete this if you want to save space!
{\large due date: \textbf{Wednesday, 24 October 2018} at the beginning of class, \\
or before that by email or canvas.

Please solve \textbf{at most 4 of the 6 exercises}!

Beware: \textbf{Collaboration is not allowed} on midterms!}
\end{center}

%----------------------------------------------------------------------------------------
%	EXERCISE 1
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 1}

\subsection{Problem}

Let $A$ and $B$ be two finite sets,
and let $f : A \to B$ be a map.

\begin{enumerate}

\item[\textbf{(a)}]
Prove that the number of maps $g : B \to A$ satisfying
$f \circ g \circ f = f$ is
\[
\abs{A}^{\abs{B \setminus f\tup{A}}}
\prod_{b \in f\tup{A}} \abs{f^{-1} \tup{b}} .
\]
(Here and in the following, $f \tup{A}$ denotes the
set $\set{ f\tup{a} \mid a \in A }$, whereas
$f^{-1} \tup{b}$ denotes the set
$\set{ a \in A \mid f \tup{a} = b }$.)

\item[\textbf{(b)}]
Prove that the number of maps $g : B \to A$ satisfying
$f \circ g \circ f = f$ and $g \circ f \circ g = g$ is
\[
\abs{f\tup{A}}^{\abs{B \setminus f\tup{A}}}
\prod_{b \in f\tup{A}} \abs{f^{-1} \tup{b}} .
\]

\end{enumerate}

[\textbf{Hint:} For part \textbf{(a)}, observe that
\[
\abs{A}^{\abs{B \setminus f\tup{A}}}
\prod_{b \in f\tup{A}} \abs{f^{-1} \tup{b}}
= \prod_{b \in B}
    \begin{cases}
    \abs{f^{-1} \tup{b}}, & \text{ if } b \in f\tup{A} ; \\
    \abs{A},              & \text{ if } b \notin f\tup{A} .
    \end{cases}
\]
What does this suggest about the construction of such
maps $g$?]

\subsection{Remark}

The maps $g$ in part \textbf{(a)} are called
``generalized inverses'' of $f$.
The maps $g$ in part \textbf{(b)} are called
``reflexive generalized inverses'' of $f$.
Note that one consequence of part \textbf{(b)}
is that there is always at least one reflexive
generalized inverse of $f$ (unless $A$ is empty).

One can similarly define generalized inverses
for linear maps between vector spaces; the resulting
notion is much more well-known and has books devoted
to it (see the
\href{https://en.wikipedia.org/wiki/Generalized_inverse}{Wikipedia}
for an overview).

\subsection{Solution}

[...]

%----------------------------------------------------------------------------------------
%	EXERCISE 2
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 2}

\subsection{Problem}

Let $n \in \NN$ and $m \in \NN$.
Prove that
\[
\tup{n+m}
\sum_{j=0}^m \tup{-1}^j \dfrac{\dbinom{m}{j}}{\dbinom{n+j}{j}}
= n .
\]

[\textbf{Hint:} The fraction on the left hand side
has too many $j$'s. Try to simplify it to get the
number of $j$'s down to just $1$ (not counting the
exponent in $\tup{-1}^j$).]

\subsection{Solution}

[...]

%----------------------------------------------------------------------------------------
%	EXERCISE 3
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 3}

\subsection{Problem}

Let $n$ be a positive integer.
Let $a_1, a_2, \ldots, a_n$ be $n$ integers.
Let $F : \ZZ \to \RR$ be any function.
Prove that
\begin{align*}
F \tup{ \max \set{a_1, a_2, \ldots, a_n} }
= \sum_{k=1}^n \tup{-1}^{k-1}
     \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n}
        F \tup{ \min \set{a_{i_1}, a_{i_2}, \ldots, a_{i_k} } } .
\end{align*}

[\textbf{Hint:}
This generalizes Exercise 5 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw2s.pdf}{Spring 2018 Math 4707 homework set \#2}.
Will some of the solutions given there still apply
to this generalization?]

\subsection{Solution}

[...]

%----------------------------------------------------------------------------------------
%	EXERCISE 4
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 4}

\subsection{Problem}

Recall once again the
\textit{\href{https://en.wikipedia.org/wiki/Fibonacci_number}{Fibonacci
sequence}} $\tup{f_0, f_1, f_2, \ldots}$, which is defined
recursively by $f_0 = 0$, $f_1 = 1$, and
\begin{equation}
f_n = f_{n-1} + f_{n-2} \qquad \text{for all } n \geq 2 .
\label{eq.fib.rec}
\end{equation}

% Now, we extend this sequence to a ``sequence infinite in
% both directions'', i.e., to a family $\tup{f_n}_{n \in \ZZ}$,
% by defining $f_n$ for \textbf{negative} integers $n$ as well.
% to do so, we simply apply \eqref{eq.fib.rec} backwards:
Now, let us define $f_n$ for \textbf{negative} integers $n$ as
well, by ``applying \eqref{eq.fib.rec} backwards'':
This means that we set $f_{n-2} = f_n - f_{n-1}$ for all
integers $n \leq 1$.
This allows us to recursively compute
$f_{-1}, f_{-2}, f_{-3}, \ldots$ (in this order).
For example,
\begin{align*}
f_{-1} &= f_1 - f_0 = 1-0 = 1; \\
f_{-2} &= f_0 - f_{-1} = 0-1 = -1; \\
f_{-3} &= f_{-1} - f_{-2} = 1 - \tup{-1} = 2,
\end{align*}
etc.

\begin{enumerate}

\item[\textbf{(a)}]
Prove that $f_{-n} = \tup{-1}^{n-1} f_n$ for each $n \in \ZZ$.

\item[\textbf{(b)}]
Prove that
$f_{n+m+1} = f_n f_m + f_{n+1} f_{m+1}$ for all
$n \in \ZZ$ and $m \in \ZZ$.

\item[\textbf{(c)}]
Prove that
$7 f_n = f_{n-4} + f_{n+4}$ for all $n \in \ZZ$.

\end{enumerate}

[\textbf{Hint:} This is \textbf{not} an exercise about the
combinatorial interpretations (domino tilings, lacunar
subsets, etc.) of Fibonacci numbers.
Make sure that your proofs cover all integers,
not just elements of $\NN$.]

\subsection{Solution}

[...]

%----------------------------------------------------------------------------------------
%	EXERCISE 5
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 5}

\subsection{Problem}

Let $n \in \NN$ and $p \in \set{0, 1, \ldots, n}$.
A \textit{$p$-derangement of $\ive{n}$}
shall mean a permutation
$\sigma$ of $\ive{n}$ such that every $i \in \ive{n-p}$
satisfies $\sigma\tup{i} \neq i+p$.
Compute the number of all $p$-derangements of $\ive{n}$
as a sum of the form $\sum_{i=0}^{n-p} \cdots$.

[\textbf{Hint:}
The case $p = 1$ was Exercise 6 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw2s.pdf}{Spring 2018 Math 4707 homework set \#2}.]

\subsection{Solution}

[...]

%----------------------------------------------------------------------------------------
%	EXERCISE 6
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 6}

\subsection{Problem}

Let $n$ and $k$ be positive integers.
A \textit{$k$-smord} will mean a $k$-tuple
$\tup{a_1, a_2, \ldots, a_k} \in \ive{n}^k$ such that no two
consecutive entries of this $k$-tuple are equal (i.e., we
have $a_i \neq a_{i+1}$ for all $i \in \ive{k-1}$).
For example, $\tup{4, 1, 4, 2, 6}$ is a $5$-smord (when
$n \geq 6$), but $\tup{1, 4, 4, 2, 6}$ is not.

It is easy to see that the number of $k$-smords is
$n \tup{n-1}^{k-1}$.
(See, e.g., Exercise 5 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw3os.pdf}{Math 4990 Fall 2017 homework set \#3}.)

A \textit{double $k$-smord} shall mean a pair
$\tup{\tup{a_1, a_2, \ldots, a_k}, \tup{b_1, b_2, \ldots, b_k}}$
of two $k$-smords
$\tup{a_1, a_2, \ldots, a_k}$ and $\tup{b_1, b_2, \ldots, b_k}$
such that every $i \in \ive{k}$ satisfies $a_i \neq b_i$.

Prove that the number of double $k$-smords is
$n \tup{n-1} \tup{n^2 - 3n + 3}^{k-1}$.

\subsection{Remark}

``Smord'' is short for ``Smirnov word'' (which is how
these tuples are sometimes called).

Double $k$-smords can also be regarded as
$2 \times k$-matrices with entries lying in $\ive{n}$
and with the property that no two adjacent entries are
equal.
(The double $k$-smord \newline
$\tup{\tup{a_1, a_2, \ldots, a_k}, \tup{b_1, b_2, \ldots, b_k}}$
thus corresponds to the $2 \times k$-matrix
$\begin{pmatrix}
a_1 & a_2 & \cdots & a_k \\
b_1 & b_2 & \cdots & b_k
\end{pmatrix}$.)

\subsection{Solution}

[...]

\end{document}


Let $x$ and $y$ be two reals.
Let $n \in \NN$.
Prove that
\[
\sum_{k=0}^n \dbinom{n}{k} \tup{x+k}^k \tup{y-k}^{n-k}
= \sum_{j=0}^n \dfrac{n!}{j!} \tup{x+y}^j .
\]

---------------------------------------------------------------------

Let $n \in \NN$.
The summation sign $\sum_{I \subseteq \ive{n}}$ shall always
stand for a sum over all subsets $I$ of $\ive{n}$.
(This sum has $2^n$ addends.)

Let $A_1, A_2, \ldots, A_n$ be $n$ numbers or
polynomials or square matrices of the same size.
(Allowing matrices means that $A_i A_j$ is not necessarily
equal to $A_j A_i$, so beware of using the binomial
formula or similar identities!)

\begin{enumerate}

\item[\textbf{(a)}]
Show that
\[
\sum_{I \subseteq \ive{n}}
 \tup{-1}^{n-\abs{I}} \tup{\sum_{i \in I} A_i}^m
 = \sum_{\substack{\tup{i_1, i_2, \ldots, i_m} \in \ive{n}^m; \\ \set{i_1, i_2, \ldots, i_m} = \ive{n}}}
   A_{i_1} A_{i_2} \cdots A_{i_m}
 \qquad \text{for all $m \in \NN$.}
\]

(Example: If $n = 2$ and $m = 3$, then this is saying
\begin{align*}
\tup{A+B}^3 - A^3 - B^3 + 0^3
&= AAB + ABA + ABB + BAA + BAB + BBA ,
\end{align*}
where we have renamed $A_1$ and $A_2$ as $A$ and $B$.)

\item[\textbf{(b)}]
Show that
\[
\sum_{I \subseteq \ive{n}}
 \tup{-1}^{n-\abs{I}} \tup{\sum_{i \in I} A_i}^m
 = 0
 \qquad \text{for all $m \in \NN$ satisfying $m < n$.}
\]

(Example: If $n = 3$ and $m = 2$, then this is saying
\begin{align*}
\tup{A+B+C}^2 - \tup{A+B}^2 - \tup{A+C}^2 - \tup{B+C}^2 + A^2 + B^2 + C^2 - 0^2
&= 0 ,
\end{align*}
where we have renamed $A_1, A_2, A_3$ as $A, B, C$.)

\item[\textbf{(c)}]
Show that
\[
\sum_{I \subseteq \ive{n}}
 \tup{-1}^{n-\abs{I}} \tup{\sum_{i \in I} A_i}^n
 = \sum_{\sigma \in S_n} A_{\sigma\tup{1}} A_{\sigma\tup{2}} \cdots A_{\sigma\tup{n}} ,
\]
where $S_n$ stands for the set of all ($n!$) permutations of $\ive{n}$.

(Example: If $n = 3$, then this is saying
\begin{align*}
& \tup{A+B+C}^3 - \tup{A+B}^3 - \tup{A+C}^3 - \tup{B+C}^3 + A^3 + B^3 + C^3 - 0^3 \\
&= ABC + ACB + BAC + BCA + CAB + CBA ,
\end{align*}
where we have renamed $A_1, A_2, A_3$ as $A, B, C$.)

\end{enumerate}

[\textbf{Hint:} You can use the \textit{product rule}, which
says the following:

\begin{proposition}[Product rule]
Let $m$ and $n$ be two nonnegative integers.
Let $P_{u,v}$, for all $u \in \ive{m}$ and $v \in \ive{n}$,
be numbers or polynomials or square matrices of the same
size. Then,
\begin{align*}
&
\tup{P_{1,1} + P_{1,2} + \cdots + P_{1,n}}
\tup{P_{2,1} + P_{2,2} + \cdots + P_{2,n}}
\cdots
\tup{P_{m,1} + P_{m,2} + \cdots + P_{m,n}}
\\
&= \sum_{\tup{i_1, i_2, \ldots, i_m} \in \ive{n}^m}
    P_{1, i_1} P_{2, i_2} \cdots P_{m, i_m} .
\end{align*}
(This frightening formula merely says that a product of
sums can be expanded, and the result will be a sum
of products, with each of the latter products being
obtained by multiplying together one addend from each sum.
You have probably used this sometime already.)
\end{proposition}
]

---------------------------------------------------------------------

Recall again the rational numbers $\dbinom{n}{k}_F$
defined on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw3.pdf}{homework set \#3}
for all $n \in \NN$ and $k \in \ZZ$ by the formula
\begin{equation}
\dbinom{n}{k}_F
=
\begin{cases}
\dfrac{f_n f_{n-1} \cdots f_{n-k+1}}{f_k f_{k-1} \cdots f_1},
   & \text{ if } n \geq k \geq 0; \\
0, & \text{ otherwise} .
\end{cases}
\label{eq.exe.fibon-coeff.neg.1}
\end{equation}
We extend this definition to the case of arbitrary
$n \in \ZZ$ (not necessarily nonnegative) by setting
\begin{equation}
\dbinom{n}{k}_F
=
\begin{cases}
\dfrac{f_n f_{n-1} \cdots f_{n-k+1}}{f_k f_{k-1} \cdots f_1},
   & \text{ if } k \geq 0; \\
0, & \text{ otherwise}
\end{cases}
\label{eq.exe.fibon-coeff.neg.2}
\end{equation}
for all $n \in \ZZ$ and $k \in \ZZ$
(using the definition of $f_n$ for negative $n$ given in the
previous exercise [!!! not quite XXX]).
Note that the formulas
\eqref{eq.exe.fibon-coeff.neg.1} and
\eqref{eq.exe.fibon-coeff.neg.2} do not clash with each other,
because in the only situation where they appear to yield
different results (viz., the situation when $k > n \geq 0$),
they still yield the same result (indeed, the second formula
yields
$\dfrac{f_n f_{n-1} \cdots f_{n-k+1}}{f_k f_{k-1} \cdots f_1}$,
which is $0$ due to the presence of the factor
$f_{n-n} = f_0 = 0$ in the numerator;
but the first formula yields $0$ because $n \geq k \geq 0$
is not satisfied).

\begin{enumerate}

\item[\textbf{(a)}]
Prove that
\[
\dbinom{n+1}{k+1}_F = \sum_{i=0}^n f_{k+2}^i f_{n-k-i-1} \dbinom{n-i}{k}_F
\]
for any nonnegative integers $n$ and $k$.

\item[\textbf{(b)}]
Prove that $\dbinom{-n}{k}_F = \tup{-1}^k \dbinom{n+k-1}{k}_F$
for all $n \in \ZZ$ and $k \in \ZZ$.

\item[\textbf{(c)}]
Prove that $\dbinom{-n}{k}_F \in \ZZ$ for
all $n \in \ZZ$ and $k \in \ZZ$.

\item[\textbf{(d)}]
Prove that
\[
\dbinom{n}{k}_F = f_{k+1} \dbinom{n-1}{k}_F + f_{n-k-1} \dbinom{n-1}{k-1}_F
\]
for any $n \in \ZZ$ and $k \in \ZZ$.

\end{enumerate}

