\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage{cancel}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, April 09, 2026 19:30:03}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
\usetikzlibrary{shapes.geometric, arrows.meta, fit, positioning, decorations.pathreplacing}
\newcounter{exer}
\newcounter{rmk}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[rmk]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\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}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
\node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\newcommand{\iverson}[1]{\left[#1\right]}
\newcommand{\sur}{\operatorname{sur}}
\newcommand{\cmark}[1]{\text{\raisebox{-0.3ex}{\tikz[baseline=(c.base)]{\node[circle,draw,inner sep=1.5pt,font=\small] (c) {$#1$};}}}}
\ihead{Math 4990 Fall 2017 (Darij Grinberg): handwritten notes 2017-10-31}
\ohead{page \thepage}
\cfoot{}
\begin{document}
\begin{center}
\textbf{Math 4990 Fall 2017 (Darij Grinberg):}
\textbf{handwritten notes from the lecture of 31 October 2017}
(digitized using Claude in 2026)
\textbf{Note:} This is \textbf{not} a polished text!
\end{center}
\subsection*{4.1. Examples (continued)}
Let us find a recursion for the numbers $c_{n}$.
\begin{center}
\begin{tikzpicture}[scale=0.8, >=Stealth]
% x-axis
\draw (-0.3,0) -- (16.5,0);
% A sample Dyck path (0,0) -> (16,0) decomposed at first return (2k,0)=(6,0)
% First part: (0,0) up to first return at (6,0), with the top shaded red
\fill[red!20] (1,1) -- (2,2) -- (3,1) -- (4,2) -- (5,1) -- cycle;
\draw[thick] (0,0) -- (1,1) -- (2,2) -- (3,1) -- (4,2) -- (5,1) -- (6,0);
\draw[thick, dotted] (1,1) -- (5,1);
% Second part: (6,0) to (16,0), shaded blue
\fill[blue!15] (6,0) -- (7,1) -- (8,2) -- (9,1) -- (10,0) -- cycle;
\fill[blue!15] (10,0) -- (11,1) -- (12,0) -- cycle;
\fill[blue!15] (12,0) -- (13,1) -- (14,2) -- (15,1) -- (16,0) -- cycle;
\draw[thick] (6,0) -- (7,1) -- (8,2) -- (9,1) -- (10,0) -- (11,1) -- (12,0)
-- (13,1) -- (14,2) -- (15,1) -- (16,0) ;
% Lattice point circles
\foreach \x/\y in {0/0,1/1,2/2,3/1,4/2,5/1,6/0,7/1,8/2,9/1,10/0,11/1,12/0,13/1,14/2,15/1,16/0} {
\node[circle, draw, fill=white, inner sep=1.5pt] at (\x,\y) {};
}
% Mark the first-return point
\node[circle, draw, fill=black, inner sep=2pt] at (6,0) {};
% Brace and labels
\draw[decorate, decoration={brace, mirror, amplitude=5pt}] (0,-1) -- node[below=5pt] {\small first $2k$ steps} (6,-1);
\draw[decorate, decoration={brace, mirror, amplitude=5pt}] (6,-1) -- node[below=5pt] {\small last $2(n-k)$ steps} (16,-1);
% Label first return
\node[below=0.2cm] at (0,0) {\small $(0,0)$};
\node[below=0.2cm] at (6,0) {\small $(2k,0)$};
\node[below=0.2cm] at (16,0) {\small $(2n,0)$};
\end{tikzpicture}
\end{center}
Fix an integer $n>0$. Each Dyck path $\left( 0,0\right) \rightarrow\left(
2n,0\right) $ returns to the $x$-axis at the point $\left( 2n,0\right) $,
but may also do so earlier. Its point of first return to the $x$-axis must
have an even $x$-coordinate (since a Dyck path always alternates between
points of the form $\left( 2i,2j\right) $ and points of the form $\left(
2i+1,2j+1\right) $; but a point of the latter kind cannot lie on the
$x$-axis); i.e., this point must have the form $\left( 2k,0\right) $ for a
given $k\in\left[ n\right] $.
Let us now see how many Dyck paths $(0,0)\rightarrow(2n,0)$ first return to
the $x$-axis at $(2k,0)$ for a given $k\in\lbrack n]$.
To construct such a path, we:
\begin{itemize}
\item first choose its first $2k$ steps: they have to form a Dyck path that
never returns to $x$-axis until $(2k,0)$; in other words, they begin with a
$\diagup$, end with a $\diagdown$, and inbetween proceed as a Dyck path
$(0,0)\rightarrow(2\left( k-1\right) ,0)$. So there are $c_{k-1}$ choices
for these first $2k$ steps.
\item then choose its last $2(n-k)$ steps: they have to proceed as a Dyck path
$(0,0)\rightarrow(2(n-k),0)$. Thus we have $c_{n-k}$ choices for them.
\end{itemize}
This shows that the \# of Dyck paths $\left( 0,0\right) \rightarrow(2n,0)$
that first return to the $x$-axis at $(2k,0)$ is $c_{k-1}c_{n-k}$. Summing
this over all $k\in\left[ n\right] $, we find%
\begin{equation}
c_{n}=\sum_{k=1}^{n}c_{k-1}\,c_{n-k}\label{eq.4990-2017oct31.1}%
\end{equation}
(since each Dyck path $\left( 0,0\right) \rightarrow\left( 2n,0\right) $
first returns to the $x$-axis at $\left( 2k,0\right) $ for some unique
$k\in\left[ n\right] $).
This gives a recursion for the numbers $c_{n}$ (with starting value $c_{0}%
=1$). Let us now solve it using generating functions.
Define the generating function%
\[
C(x)=\sum_{n\geq0}c_{n}x^{n}=c_{0}+c_{1}x+c_{2}x^{2}+\cdots.
\]
By (\ref{eq.4990-2017oct31.1}) and by $c_{0}=1$, this becomes%
\begin{align}
C(x) & =1+(c_{0}c_{0})x+(c_{0}c_{1}+c_{1}c_{0})x^{2}+(c_{0}c_{2}+c_{1}%
c_{1}+c_{2}c_{0})x^{3}+\cdots\nonumber\\
& =1+x\underbrace{(c_{0}+c_{1}x+c_{2}x^{2}+\cdots)^{2}}_{=(C(x))^{2}%
}\nonumber\\
& =1+x\left( C(x)\right) ^{2}.\label{eq.4990-2017oct31.2}%
\end{align}
This is a quadratic equation in $C(x)$. Solve it (let's be optimistic and
consider this to be allowed). Get%
\begin{equation}
C(x)=\dfrac{1\pm\sqrt{1-4x}}{2x}\,.\label{eq.4990-2017oct31.3}%
\end{equation}
The $\pm$ sign here cannot be $+$, because with a $+$ sign, the power series
on top of the fraction would not be divisible by $2x$. So it must be a $-$.
Thus we have%
\begin{equation}
C(x)=\dfrac{1-\sqrt{1-4x}}{2x}=\dfrac{1}{2x}\left( 1-(1-4x)^{1/2}\right)
.\label{eq.4990-2017oct31.4}%
\end{equation}
Now recall the binomial formula%
\begin{equation}
(1+x)^{n}=\sum_{k=0}^{n}\dbinom{n}{k}x^{k}=\sum_{k}\dbinom{n}{k}%
x^{k},\label{eq.4990-2017oct31.5}%
\end{equation}
which holds for all $n\in\mathbb{N}$. Let's pretend that it works for $n=1/2$,
too. Thus,%
\begin{equation}
(1+x)^{1/2}=\sum_{k}\dbinom{1/2}{k}x^{k}.\label{eq.4990-2017oct31.6}%
\end{equation}
Now, substitute $-4x$ for $x$ here, to get%
\[
(1-4x)^{1/2}=\sum_{k}\dbinom{1/2}{k}(-4x)^{k}=\sum_{k}\dbinom{1/2}{k}%
(-4)^{k}x^{k}.
\]
So our formula (\ref{eq.4990-2017oct31.4}) for $C(x)$ becomes%
\begin{align}
C(x) & =\dfrac{1}{2x}\underbrace{\left( 1-\sum_{k}\dbinom{1/2}{k}%
(-4)^{k}x^{k}\right) }_{=-\sum\limits_{k\geq1}\dbinom{1/2}{k}(-4)^{k}x^{k}%
}\nonumber\\
& =-\sum_{k\geq1}\dbinom{1/2}{k}(-4)^{k}x^{k}\cdot\dfrac{1}{2x}\nonumber\\
& =-\sum_{k\geq1}\dbinom{1/2}{k}\dfrac{(-4)^{k}}{2}x^{k-1}\nonumber\\
& =-\sum_{k\geq0}\dbinom{1/2}{k+1}\dfrac{(-4)^{k+1}}{2}x^{k}%
\,.\label{eq.4990-2017oct31.9}%
\end{align}
Now, comparing coefficients before $x^{n}$ on both sides of this equality
gives%
\begin{align*}
c_{n} & =-\underbrace{\dbinom{1/2}{n+1}}_{\substack{=\dfrac{1/2}{n+1}%
\dbinom{-1/2}{n}\\\text{(by the absorption formula)}}}\dfrac{(-4)^{n+1}}{2}\\
& =-\dfrac{1/2}{n+1}\underbrace{\dbinom{-1/2}{n}}_{\substack{=\dbinom{2n}%
{n}\left( -\dfrac{1}{4}\right) ^{n}\\\text{(by HW2 exercise 1)}}%
}\dfrac{(-4)^{n+1}}{2}\\
& =-\dfrac{1/2}{n+1}\dbinom{2n}{n}\left( -\dfrac{1}{4}\right) ^{n}%
\cdot\dfrac{(-4)^{n+1}}{2}\\
& =\dfrac{1}{n+1}\dbinom{2n}{n}\cdot\underbrace{\underbrace{\dfrac{-1/2}{2}%
}_{=-\dfrac{1}{4}}\underbrace{\left( -\dfrac{1}{4}\right) ^{n}(-4)^{n+1}%
}_{=-4}}_{=1}\\
& =\dfrac{1}{n+1}\dbinom{2n}{n}=\dbinom{2n}{n}-\dbinom{2n}{n-1}.
\end{align*}
\subsubsection*{Example 3: Chu--Vandermonde convolution revisited}
Theorem 3.12 (that is, Theorem\ 12 in Chapter\ 3) says that%
\[
\dbinom{a+b}{n}=\sum_{k=0}^{n}\dbinom{a}{k}\dbinom{b}{n-k}\qquad
\forall\,a,b\in\mathbb{N},\quad n\in\mathbb{N}.
\]
We can reprove this using FPSs (= formal power series).
Namely, we clearly have
\[
(1+x)^{a}\,(1+x)^{b}=(1+x)^{a+b}.
\]
In view of%
\begin{align*}
(1+x)^{a} & =\sum_{k}\dbinom{a}{k}x^{k}\ \ \ \ \ \ \ \ \ \ \text{and}\\
(1+x)^{b} & =\sum_{k}\dbinom{b}{k}x^{k}\ \ \ \ \ \ \ \ \ \ \text{and}\\
(1+x)^{a+b} & =\sum_{k}\dbinom{a+b}{k}x^{k}=\sum_{n}\dbinom{a+b}{n}x^{n},
\end{align*}
we can rewrite this as%
\[
\left( \sum_{k}\dbinom{a}{k}x^{k}\right) \left( \sum_{k}\dbinom{b}{k}%
x^{k}\right) =\sum_{n}\dbinom{a+b}{n}x^{n}.
\]
Hence,%
\begin{align*}
\sum_{n}\dbinom{a+b}{n}x^{n} & =\left( \sum_{k}\dbinom{a}{k}x^{k}\right)
\left( \sum_{k}\dbinom{b}{k}x^{k}\right) \\
& =\sum_{k,\ell}\dbinom{a}{k}x^{k}\dbinom{b}{\ell}x^{\ell}\\
& =\sum_{k,\ell}\dbinom{a}{k}\dbinom{b}{\ell}x^{k+\ell}\\
& =\sum_{n}\left( \sum_{k=0}^{n}\dbinom{a}{k}\dbinom{b}{n-k}\right) x^{n}\ .
\end{align*}
Comparing coefficients yields $\dbinom{a+b}{n}=\sum\limits_{k=0}^{n}\dbinom
{a}{k}\dbinom{b}{n-k}$.
\subsubsection*{Example 4: a recursive sequence}
This example is from Wilf's \textquotedblleft
generatingfunctionology\textquotedblright\ \cite[\S 1.2]{Wilf04}.
Define a sequence $(a_{0},a_{1},a_{2},\ldots)$ recursively by%
\[
a_{0}=1\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ a_{n+1}%
=2a_{n}+n\ \ \ \ \ \ \ \ \ \ \text{for all }n\geq0.
\]
This sequence it starts out $1,2,5,12,27,58,121,\ldots$.
(In the OEIS, it appears as \href{https://oeis.org/A000325}{A000325}, with its
indexing shifted.)
Can we find a closed form for $a_{n}$ ?
Define the generating function
\[
A(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots.
\]
Thus,%
\begin{align}
A(x) & =1+(\underline{2a_{0}}+0)x+(\underline{2a_{1}}+1)x^{2}%
+(\underline{2a_{2}}+2)x^{3}+\cdots\nonumber\\
& =1+\underline{2(a_{0}x+a_{1}x^{2}+a_{2}x^{3}+\cdots)}+(0x+1x^{2}%
+2x^{3}+\cdots)\nonumber\\
& =1+2x\,A(x)+x(0+1x+2x^{2}+3x^{3}+\cdots)\ .\label{eq.4990-2017oct31.15}%
\end{align}
Now, what is the series $0+1x+2x^{2}+3x^{3}+\cdots$ ?
Here are two ways to compute it:
\begin{enumerate}
\item We have%
\begin{align}
& 0+1x+2x^{2}+3x^{3}+\cdots\nonumber\\
& =x\underbrace{\left( 1+2x+3x^{2}+\cdots\right) }_{\substack{=\left(
1+x+x^{2}+x^{3}+\cdots\right) ^{\prime}\\=\left( \dfrac{1}{1-x}\right)
^{\prime}=\dfrac{1}{\left( 1-x\right) ^{2}}\\\text{(by the standard rules
for derivatives)}}}\nonumber\\
& =x\cdot\dfrac{1}{\left( 1-x\right) ^{2}}.\label{eq.4990-2017oct31.16}%
\end{align}
\item We have
\begin{align*}
& 0+1x+2x^{2}+3x^{3}+\cdots\\
& =x+x^{2}+x^{3}+x^{4}+\cdots\\
& \qquad+x^{2}+x^{3}+x^{4}+\cdots\\
& \qquad\qquad+x^{3}+x^{4}+\cdots\\
& \qquad\qquad\qquad\ +x^{4}+\cdots\\
& \qquad\qquad\qquad\qquad+\cdots\\
& =x\left( 1+x+x^{2}+x^{3}+\cdots\right) \\
& \qquad+x^{2}\left( 1+x+x^{2}+x^{3}+\cdots\right) \\
& \qquad\qquad+x^{3}\left( 1+x+x^{2}+x^{3}+\cdots\right) \\
& \qquad\qquad\qquad+x^{4}\left( 1+x+x^{2}+x^{3}+\cdots\right) \\
& \qquad\qquad\qquad\qquad+\cdots\\
& =x\cdot\dfrac{1}{1-x}+x^{2}\cdot\dfrac{1}{1-x}+x^{3}\cdot\dfrac{1}%
{1-x}+\cdots\\
& =\underbrace{\left( x+x^{2}+x^{3}+\cdots\right) }_{=x\cdot\dfrac{1}{1-x}%
}\cdot\,\dfrac{1}{1-x}=x\cdot\dfrac{1}{(1-x)^{2}}\,.
\end{align*}
Of course, this recovers (\ref{eq.4990-2017oct31.16}) again.
\end{enumerate}
[But be careful with infinite sums.]
So our formula (\ref{eq.4990-2017oct31.6}) for $A(x)$ becomes%
\[
A(x)=1+2x\,A(x)+x\cdot x\cdot\dfrac{1}{(1-x)^{2}}\,.
\]
This is a linear equation in $A(x)$. Solving it yields%
\begin{align*}
A(x) & =\dfrac{1-2x+2x^{2}}{(1-x)^{2}(1-2x)}=\underbrace{\dfrac{-1}%
{(1-x)^{2}}}_{\substack{=-(1+2x+3x^{2}+\cdots)\\\text{(as we saw above)}%
}}+\underbrace{\dfrac{2}{1-2x}}_{=2\sum\limits_{k}(2x)^{k}=\sum\limits_{k}%
2^{k+1}x^{k}}\\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left( \text{by partial fraction
decomposition}\right) \\
& =-\underbrace{(1+2x+3x^{2}+\cdots)}_{=\sum\limits_{k}\left( k+1\right)
x^{k}}+\sum\limits_{k}2^{k+1}x^{k}\\
& =\sum_{k}(2^{k+1}-(k+1))x^{k}\,.
\end{align*}
Comparing coefficients yields%
\[
a_{n}=2^{n+1}-(n+1)\qquad\text{for all }n\in\mathbb{N}.
\]
\subsubsection*{Example 0: counting compositions using FPSs}
Let $k(n)$ be the \# of compositions of $n$. Let's find a formula for $k(n)$.
Set
\[
K(x)=k(0)+k(1)x+k(2)x^{2}+\cdots.
\]
Thus,%
\begin{align*}
K(x) & =\sum_{n\geq0}k(n)x^{n}=\sum_{n\geq0}\;\sum_{\substack{(a_{1}%
,a_{2},\ldots,a_{k})\\\text{composition of }n}}x^{n}\\
& =\sum_{n\geq0}\;\sum_{\substack{(a_{1},a_{2},\ldots,a_{k}%
)\\\text{composition of }n}}x^{a_{1}+a_{2}+\cdots+a_{k}}=\sum
_{\substack{(a_{1},a_{2},\ldots,a_{k})\\\text{composition}\\\text{(i.e.\ tuple
of}\\\text{positive\ integers)}}}x^{a_{1}+a_{2}+\cdots+a_{k}}\\
& =\sum_{k\geq0}\;\underbrace{\sum_{\substack{(a_{1},a_{2},\ldots,a_{k}%
)\in\{1,2,3,\ldots\}^{k}}}x^{a_{1}+a_{2}+\cdots+a_{k}}}_{\substack{=\left(
\sum_{a=1}^{\infty}x^{a}\right) ^{k}\\\text{(by the product rule)}}%
}=\sum_{k\geq0}\left( \sum_{a=1}^{\infty}x^{a}\right) ^{k}\\
& =\dfrac{1}{1-\sum_{a=1}^{\infty}x^{a}}\qquad\left( \text{since }%
\sum_{k\geq0}y^{k}=\dfrac{1}{1-y}\right) \\
& =\dfrac{1}{1-\left( \dfrac{1}{1-x}-1\right) }\qquad\left( \text{since
}\sum_{a=1}^{\infty}x^{a}=\sum_{a\geq0}x^{a}-1=\dfrac{1}{1-x}-1\right) \\
& =\dfrac{1}{2-\dfrac{1}{1-x}}=\dfrac{1-x}{2(1-x)-1}=\dfrac{1-x}%
{1-2x}=1+x\cdot\dfrac{1}{1-2x}\\
& =1+x\sum_{k\geq0}(2x)^{k}\qquad\left( \text{since }\dfrac{1}{1-y}%
=\sum_{k\geq0}y^{k}\right) \\
& =1+\sum_{k}2^{k}x^{k+1}=\sum_{k}%
\begin{cases}
2^{k-1}, & \text{if }k>0;\\
1, & \text{if }k=0
\end{cases}
\;\cdot\;x^{k}\,.
\end{align*}
Comparing coefficients here, we obtain%
\[
k(n)=%
\begin{cases}
2^{n-1}, & \text{if }n>0;\\
1, & \text{if }n=0.
\end{cases}
\]
\subsection*{4.2. The Concept of a FPS (formal power series)}
\medskip We now want to give a definition of a FPS and also justifications for
the things we did to FPS (dividing, quadratic equations, infinite sums,
$\ldots$).
First things first: FPS are not functions. You cannot substitute $x=2$ into
$\dfrac{1}{1-x}=1+x+x^{2}+\cdots$ and \textquotedblleft
obtain\textquotedblright\ $\dfrac{1}{-1}=1+2+4+8+16+\cdots$.
Let us go back to abstract algebra.
\begin{definition}
\label{def.cring}
A \emph{commutative ring} is, informally, a set $K$ equipped with three binary
operations $\oplus$, $\ominus$ and $\odot$ and two elements $\cmark{0}$
and $\cmark{1}$ that ``behave'' like addition, subtraction and multiplication
of numbers and like the numbers $0$ and $1$, respectively.
For example, they have to satisfy rules like
$\tup{a \oplus b} \odot c = \tup{a \odot c} \oplus \tup{b \odot c}$.
Formally, a \emph{commutative ring} is a set $K$ equipped with maps
\begin{align*}
\oplus &: K \times K \to K, \\
\ominus &: K \times K \to K, \\
\odot &: K \times K \to K
\end{align*}
and elements $\cmark{0}\in K$ and $\cmark{1}\in K$ satisfying the following
axioms (for all $a,b,c \in K$):
\begin{enumerate}
\item[\textbf{(a)}] Commutativity of $\oplus$:\quad $a\oplus b=b\oplus a$.
\item[\textbf{(b)}] Associativity of $\oplus$:\quad $a\oplus(b\oplus
c)=(a\oplus b)\oplus c$.
\item[\textbf{(c)}] Neutrality of $\cmark{0}$:\quad $a\oplus\cmark{0}
=\cmark{0}\oplus a=a$.
\item[\textbf{(d)}] $\ominus$ undoes $\oplus$:\quad $a\oplus b=c
\Longleftrightarrow a=c\ominus b$.
% \quad(Most authors do this part
% differently, but the end result is the same.)
\item[\textbf{(e)}] Commutativity of $\odot$:\quad $a\odot b=b\odot a$.
\item[\textbf{(f)}] Associativity of $\odot$:\quad $a\odot(b\odot c)=(a\odot
b)\odot c$.
\item[\textbf{(g)}] Distributivity:\quad $a\odot(b\oplus c)=(a\odot b)\oplus
(a\odot c)$; \\
\phantom{zx}\qquad\qquad\qquad
$(a\oplus b)\odot c=(a\odot c)\oplus(b\odot c)$.
\item[\textbf{(h)}] Neutrality of $\cmark{1}$:\quad $a\odot\cmark{1}=
\cmark{1}\odot a =a$.
\item[\textbf{(i)}] Annihilation:\quad $a\odot\cmark{0}=\cmark{0}
\odot a=\cmark{0}$.
\end{enumerate}
(Most authors do this definition differently: Instead of requiring
a binary map $\ominus$ satisfying axiom \textbf{(d)},
they demand the ``existence of additive
inverses'', meaning that for each $a \in K$ there exists an
$a' \in K$ satisfying $a \oplus a' = a' \oplus a = \cmark{0}$.
In this case, $a'$ is necessarily unique, and the binary map
$\ominus$ can be defined by $a \ominus b = a \oplus b'$.
Conversely, given a commutative ring $K$ defined in our way,
using $\ominus$, we can easily verify the ``existence of additive
inverses'' by taking $a' = \cmark{0}\ominus a$. Thus, the two
definitions are equivalent, i.e., the end-result is the same.)
\end{definition}
\textbf{Examples of commutative rings}
include $\ZZ$, $\QQ$, $\RR$, $\CC$.
\textbf{Non-examples of commutative rings}
include $\NN$ (a semiring, not a ring, for lack of subtraction);
the matrix ring $M^{m\times m}$ (a noncommutative ring) for $m>1$.
Usually, the circles in Definition~\ref{def.cring} get dropped
-- i.e., we write $\oplus$, $\ominus$, $\odot$, $\cmark{0}$,
$\cmark{1}$ as $+$, $-$, $\cdot$, $0$ and $1$.
The $\cdot$ sign is often omitted -- i.e., we write $ab$
for $a \cdot b$ (that is, $a \odot b$).
Furthermore, the ``PEMDAS convention'' for order of operations is
commonly used in a commutative ring just as it is for numbers;
for example, the expression $a\cdot b + c\cdot d$ means
$\tup{a \cdot b} + \tup{c \cdot d}$.
For more about commutative rings, see \cite[Section 6.1]{detnotes}.
\begin{statement}
\textbf{Good news:} In an arbitrary commutative ring,
the standard rules of computation apply:
You can compute finite sums without caring about
the order of summation or parenthesization: for
example, we have
\begin{align}
((a+(b+c))+d) + e
= (a+b) + (c+(d+e))
\label{eq.4990-2017oct31.ga1}
\end{align}
and similar identities
(``general associativity''), so you can just
write $a+b+c+d+e$ for both sides of
\eqref{eq.4990-2017oct31.ga1}. Also, we have
\[
a+b+c+d+e=d+b+a+e+c
\]
and similar identities
(``general commutativity'').
The same applies to finite products.
\end{statement}
\begin{thebibliography}{99999999} %
\bibitem[Grinbe15]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 15 September 2022.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf} \newline The
numbering of theorems and formulas in this link might shift when the project
gets updated; for a \textquotedblleft frozen\textquotedblright\ version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2022-09-15c} .
\bibitem[Wilf04]{Wilf04}Herbert S. Wilf, \textit{generatingfunctionology}, 2nd
edition 2004.\newline\url{https://www2.math.upenn.edu/~wilf/DownldGF.html}
\end{thebibliography}
\end{document}