
\documentclass[12pt]{amsart}
\usepackage{amsmath, amsthm, amssymb, amsfonts}
\usepackage{enumerate}
\usepackage{hyperref}
\usepackage{mathabx} %needed for \ibra
\usepackage{rotating} %needed for \sideways
\usepackage{verbatim}

%%%Document Configuration
\pagestyle{plain} %Use empty for no page numbers.
%The initial page is special, see \thispagestyle below.
%\addtolength{\topmargin}{-.5in}
\textwidth = 6in
\oddsidemargin = .25in
\evensidemargin = .25in
\voffset = -1in
\textheight = 9.5 in
%\textwidth = 6in
%\parindent = 0in
%\headsep = 0in
\relpenalty = 9999
\binoppenalty = 9999
%linespacing
\renewcommand{\baselinestretch}{1.25}
\reversemarginpar
%%%

%%%Theorem Configuration
\theoremstyle{plain}
\newtheorem*{main}{Main~Theorem}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\theoremstyle{definition}
\newtheorem{dfn}[thm]{Definition}
\newtheorem*{rem*}{Remark}
%%%

%%%bootstrap definitions
\DeclareSymbolFont{cmttsymbols}{OT1}{cmtt}{m}{n}
\DeclareMathSymbol{\modtemp}{\mathbin}{cmttsymbols}{"25} %used for \mod
\DeclareMathDelimiter{\sll}{\mathopen}{cmttsymbols}{"5B}{cmttsymbols}{"5B}
\DeclareMathDelimiter{\slr}{\mathclose}{cmttsymbols}{"5D}{cmttsymbols}{"5D}
\newcommand{\sld}[1]{\raisebox{-2pt}{\resizebox{!}{12 pt}{$#1$}}}
\newcommand{\co}{:}
%%%

%%%proper name definitions
\newcommand{\Ro}{R\o{}dseth}
%%%

%%%semantic definitions
\DeclareMathOperator{\Frac}{frac}
\DeclareMathOperator{\IH}{IH}
\DeclareMathOperator{\realpart}{Re}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\half}{\tfrac{1}{2}}
\newcommand{\height}[1]{\makebox[0pt]{\phantom{\mbox{$\displaystyle #1$}}}}
\newcommand{\integer}{\mathbb{Z}}
\newcommand{\set}[2]{\left\{ #1 \left|~#2 \height{\Big|#1}\right\}\right.}
%\newcommand{\slice}[1]{\left\sll#1\height{\Huge|}\right\slr}
\newcommand{\slice}[1]{\sld{\sll}#1\sld{\slr}}
\renewcommand{\natural}{\mathbb{N}}
%%%

%%%local definitions
\newcommand{\cl}[1]{\overline{#1}}
\newcommand{\diff}{\Delta}
\newcommand{\eps}{\epsilon}
\newcommand{\epsv}{\varepsilon}
\newcommand{\eqand}{\hspace{1pc}\text{and}\hspace{1pc}}
\newcommand{\ibra}[1]{\ldbrack{#1}\rdbrack}
\newcommand{\lhs}{\text{LHS}}
\newcommand{\ltlex}{\leq_{\text{lex}}}
\newcommand{\Let}{\text{ let }}
\renewcommand{\mod}{\modtemp}
\newcommand{\constmfour}{\left({b+1\choose2}+b\right)}
\newcommand{\one}[1]{\fbox{$\displaystyle \frac{#1}{#1}$}}
\newcommand{\pg}[3]{B_{#1}(#2, #3)}
\newcommand{\pgbq}[1]{B_b({#1}, q)}
\newcommand{\R}{R_b}
\newcommand{\seq}[2]{\left( #1 \left|~#2 \height{\Big|#1}\right)\right.}
\newcommand{\shr}{\texttt{>>}}
\newcommand{\shl}{\texttt{<<}}
\renewcommand{\Re}{\realpart}
\newcommand{\tab}{\hspace{2pc}}
\newcommand{\thih}[3]{\sum_{j=0}^{#1}\alpha_jp_b(b^j#2#3)}
\newcommand{\Trp}[2]{\genfrac{\backslash}{/}{0pt}{}{#1}{#2}}
%%%

\begin{document}

\title{Problems in Restricted Partitions}
\author{Dakota Blair}
\begin{abstract}
This note contains discussion on problems concerning partitions whose parts are
powers of a given base $b$.
\end{abstract}
\maketitle

\begin{lem}
\label{lem:evalsum}
\[
%\sum_{k = 1}^{b-1}\R(2, n, k) = (b-1)\R(2, n-1, 0) + {b \choose 2}\R(1, n-1, 0)
\sum_{k=1}^{b-1}p_b(b^2n-kb) = (b-1)p_b(b^2(n-1)) + {b \choose 2}p_b(b(n-1))
\]
\end{lem}

\begin{proof}
Note that when $1 < k < b$
\begin{align*}
p_b(b^2n-kb)
 & = p_b(b^2 n - (k+1)b) + p_b(bn - k)\\
 & = p_b(b^2 n - (k+1)b) + p_b(bn - \floor{\frac{k}{b}}b)\\
 & = p_b(b^2 n - (k+1)b) + p_b(bn - b)\\
 & = p_b(b^2 n - (k+1)b) + p_b(bn - bb^0)\\
 & = p_b(b^2 n - (k+1)b) + p_b(b(n-1))\\
\end{align*}

Therefore
\begin{align*}
\sum_{k = 1}^{b-1}p_b(b^2 n - kb)
 & = \sum_{k = 1}^{b-1}(p_b(b^2 n - (k+1)b) + p_b(b(n-1))) \text{ (descend)}\\
 & = (b-1) p_b(b(n-1)) + \sum_{k = 1}^{b-1}p_b(b^2 n - (k+1)b) \text{ (pop)}\\
 & = (b-1) p_b(b(n-1)) + p_b(b^2 n - b^2) + \sum_{k = 1}^{b-2}p_b(b^2 n - (k+1)b)\\
 & = (b-1) p_b(b(n-1)) + p_b(b^2(n-1)) + \sum_{k = 1}^{b-2}p_b(b^2 n - (k+1)b) \text{ (reindex)}\\
 & = (b-1) p_b(b(n-1)) + p_b(b^2(n-1)) + \sum_{k = 2}^{b-1}p_b(b^2 n - kb)\text{ (descend, pop, reindex)} \\
 & = ((b-1) + (b-2)) p_b(b(n-1)) + 2p_b(b^2(n-1)) + \sum_{k = 3}^{b-1}p_b(b^2 n - kb)\\
 & = \cdots \text{descend, pop, reindex a total of $b-1$ times}\\
 & = {b \choose 2}p_b(b(n-1)) + (b-1)p_b(b^2(n-1))\\
 & = (b-1)p_b(b^2(n-1)) + {b \choose 2} p_b(b(n-1))\\
\end{align*}
\end{proof}

\begin{dfn}[The recurrence applied $l$ times]
\[
F^l(p_b(b^m n)) = p_b(b^m n - bl) + \sum_{k = 0}^{l -1}p_b(b^{m-1}n - k)
\]
\end{dfn}

\begin{thm}
%\label{thm:m=3}
\[
f_3(b, q)B_b(q) = (1-q)^3\pg{b}{q}{b^3}
\]
where
\[
f_3(b,q) = 1 + \half(b-1)\left((b^2+2b+4)q + (b^2-2)q^2\right)
\]
\end{thm}

\begin{proof}

\begin{align*}
p_b(b^3 n)
 & = p_b(b^3 n - b) + p_b(b^2 n)= F(p_b(b^3 n))\\
 & = p_b(b^3 n - b^3) + \sum_{k = 0}^{b^2-1}p_b(b^{2}n - k) = F^{b^2}(p_b(b^3 n))\\
 & = p_b(b^3(n - 1)) + \sum_{k = 0}^{b^2-1}p_b(b^{2}n - k)\\
 & = p_b(b^3(n - 1)) + \sum_{k = 0}^{b^2-1}p_b(b^{2}n - \ceil{\frac{k}{b}}b)\\
 & = p_b(b^3(n - 1)) + p_b(b^2n) + \sum_{k = 1}^{b^2-1}p_b(b^{2}n - \ceil{\frac{k}{b}}b)\\
 & = p_b(b^3(n - 1)) + p_b(b^2n) + \sum_{k = 1}^{(b-1)(b+1)}p_b(b^{2}n - \ceil{\frac{k}{b}}b)\\
 & = p_b(b^3(n - 1)) + p_b(b^2n) + (b-1)p_b(b^2n - b^2) + \sum_{k = 1}^{(b-1)(b)}p_b(b^{2}n - \ceil{\frac{k}{b}}b)\\
 & = p_b(b^3(n - 1)) + p_b(b^2n) + (b-1)p_b(b^2(n - 1)) + \sum_{k = 1}^{(b-1)(b)}p_b(b^{2}n - \ceil{\frac{k}{b}}b)\\
 & = p_b(b^3(n - 1)) + p_b(b^2n) + (b-1)p_b(b^2(n - 1)) + b\sum_{k = 1}^{b-1}p_b(b^{2}n - kb)\\
 & \tab \text{ (so by Lemma \ref{lem:evalsum})}\\
 & = p_b(b^3(n - 1)) + p_b(b^2n) + (b-1)p_b(b^2(n - 1)) + b\left((b-1)p_b(b^2(n-1)) + {b \choose 2}p_b(b(n-1))\right)\\
p_b(b^3 n)
 & = p_b(b^3(n - 1)) + p_b(b^2n) + (b+1)(b-1)p_b(b^2(n - 1)) + b{b \choose 2}p_b(b(n-1))\\
\end{align*}

Finally, upon passing to generating functions:
\begin{align*}
\pgbq{3} & = q\pgbq{3} + \pgbq{2} + (b+1)(b-1)q\pgbq{2} + b{b \choose 2}q\pgbq{1}\\
(1-q)\pgbq{3} & = (1 + (b+1)(b-1)q)\pgbq{2} + b{b \choose 2}q\pgbq{1}\\
(1-q)\pgbq{3} & = (1 + (b+1)(b-1)q)\frac{1+(b-1)q}{(1-q)^2}B_b(q) + b{b \choose 2}q(1-q)^{-1}B_b(q)\\
(1-q)^3\pgbq{3} & = (1 + (b+1)(b-1)q)(1+(b-1))qB_b(q) + b{b \choose 2}q(1-q)B_b(q)\\
(1-q)^3\pgbq{3} & = \left(1 + \left((b^2-1) + (b-1) + b{b \choose 2}\right)q + \left((b^2-1)(b-1) - b{b \choose 2}\right)q^2\right)B_b(q)\\
(1-q)^3\pgbq{3} & = \left(1
    + \left(\half(b-1)(b^2+2b+4)\right)q
    + \left(\half(b-1)(b^2-2)\right)q^2
\right)B_b(q)\\
(1-q)^3\pgbq{3}
& = \left(1 + (\half(b-1)\left(
    + (b^2+2b+4)q
    + (b^2-2)q^2
    \right)\right)B_b(q)
\end{align*}
\end{proof}

\begin{lem}
\label{lem:lessk=dubsum}
\begin{align*}
 \sum_{k=1}^{b^{m-a}}\sum_{j=0}^{k-1}\ibra{k\geq j}p_b(b^{m-a}(n-1)+k-j)
 & = \sum_{j=1}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j) \text{ moreover}\\
 & = \sum_{k=1}^{b^{m-a}-1}kp_b(b^{m-a}n-k)\\
\end{align*}
\end{lem}
\begin{proof}
\begin{align*}
\lhs
 & = \sum_{k=1}^{b^{m-a}}\sum_{j=0}^{k-1}\ibra{k\geq j}p_b(b^{m-a}(n-1)+k-j)\Let u=k-j\\
 & = \sum_{k=1}^{b^{m-a}-1}\sum_{u=1}^{k}\ibra{u\geq0}p_b(b^{m-a}(n-1)+u)\Let j = u\\
 & = \sum_{k=1}^{b^{m-a}-1}\sum_{j=1}^{k}\ibra{1\leq j\leq k}p_b(b^{m-a}(n-1)+j)\\
 & = \sum_{k=1}^{b^{m-a}-1}\sum_{j=1}^{b^{m-a}-1}\ibra{1\leq j\leq k}p_b(b^{m-a}(n-1)+j)\\
 & = \sum_{j=1}^{b^{m-a}-1}\sum_{k=1}^{b^{m-a}-1}\ibra{1\leq j\leq k}p_b(b^{m-a}(n-1)+j)\\
 & = \sum_{j=1}^{b^{m-a}-1}p_b(b^{m-a}(n-1)+j)\sum_{k=1}^{b^{m-a}-1}\ibra{1\leq j\leq k}\\
 & = \sum_{j=1}^{b^{m-a}-1}p_b(b^{m-a}(n-1)+j)\sum_{k=j}^{b^{m-a}-1}1\\
%& = \sum_{j=1}^{b^{m-a}-1}p_b(b^{m-a}(n-1)+j)(b^{m-a}-1-j+1)\\%\star why?
 & = \sum_{j=1}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)\\
\end{align*}

Then
\begin{align*}
\lhs
 & = \sum_{k=1}^{b^{m-a}}\sum_{j=0}^{k-1}\ibra{k\geq j}p_b(b^{m-a}(n-1)+k-j)\\
 & = \sum_{j=1}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j) \Let k=b^{m-a}-j\\
 & = \sum_{k=1}^{b^{m-a}-1}kp_b(b^{m-a}(n-1)+b^{m-a}-k)\\
 & = \sum_{k=1}^{b^{m-a}-1}kp_b(b^{m-a}n-k)\\
\end{align*}
\end{proof}

\begin{cor}
\label{cor:fac+j}
\begin{align*}
\sum_{j=1}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)
 & = \left({b^{m-a}\choose2}-{b^{m-a}-b+1\choose 2}\right)p_b(b^{m-a}(n-1))\\
 & \tab + \ibra{m>a+1}\sum_{j=b}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)\\
\end{align*}
\end{cor}

\begin{proof}
Splitting the sum reveals
\begin{align*}
\sum_{j=1}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)
 & = \sum_{j=1}^{b-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)\\
 & \tab + \ibra{m>a+1}\sum_{j=b}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)\\
\end{align*}
Then the first term becomes
\begin{align*}
\lhs
 & = \sum_{j=1}^{b-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)\\
 & = \sum_{j=1}^{b-1}(b^{m-a}-j)p_b(b^{m-a}(n-1))\\
 & = p_b(b^{m-a}(n-1))\sum_{j=1}^{b-1}(b^{m-a}-j)\\
 & = p_b(b^{m-a}(n-1))\sum_{j=b^{m-a}-b+1}^{b^{m-a}-1}j\\
 & = \left({b^{m-a} \choose 2} - {b^{m-a}-b+1\choose 2}\right)p_b(b^{m-a}(n-1))
\end{align*}
Thus
\begin{align*}
\sum_{j=1}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)
 & = \left({b^{m-a}\choose2}-{b^{m-a}-b+1\choose 2}\right)p_b(b^{m-a}(n-1))\\
 & \tab + \ibra{m>a+1}\sum_{j=b}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)\\
\end{align*}
\end{proof}

\begin{thm}
\label{thm:+kb}
\begin{align*}
\sum_{k=1}^{b^{m-a}-1}p_b(b^{m-a+1}(n-1)+kb)
 & = (b^{m-a}-1)p_b(b^{m-a+1}(n-1)) + \sum_{k=1}^{b^{m-a}}kp_b(b^{m-a}n-k)\\
 & = (b^{m-a}-1)p_b(b^{m-a+1}(n-1))\\
 & \tab + \left({b^{m-a}\choose2}-{b^{m-a}-b+1\choose2}\right)p_b(b^{m-a}(n-1))\\
 & \tab + \ibra{m>a+1}\sum_{j=b}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)\\
\end{align*}
\end{thm}

\begin{proof}
\begin{align*}
\lhs
 & = \sum_{k=1}^{b^{m-a}-1}p_b(b^{m-a+1}(n-1)+kb)\\
 & = \sum_{k=1}^{b^{m-a}-1}\left(p_b(b^{m-a+1}(n-1)+(k-1)b) + p_b(b^{m-a}(n-1)+k)\right)\\
 & = \sum_{k=1}^{b^{m-a}-1}\left(\ibra{k>a}p_b(b^{m-a+1}(n-1)+(k-2)b) + p_b(b^{m-a}(n-1)+k-1) + p_b(b^{m-a}(n-1)+k)\right)\\
 & = \sum_{k=1}^{b^{m-a}-1}\left(p_b(b^{m-a+1}(n-1)+(k-2)) + \sum_{j=0}^1\ibra{k\geq j}p_b(b^{m-a}(n-1)+k-j)\right)\\
 & \ldots\\
 & = \sum_{k=1}^{b^{m-a}-1}\left(p_b(b^{m-a+1}(n-1)) + \sum_{j=0}^{k-1}\ibra{k\geq j}p_b(b^{m-a}(n-1)+k-j)\right)\\
 & = (b^{m-a}-1)p_b(b^{m-a+1}(n-1)) + \sum_{k=1}^{b^{m-a}}\sum_{j=0}^{k-1}\ibra{k\geq j}p_b(b^{m-a}(n-1)+k-j)\\
\end{align*}

By Lemma \ref{lem:lessk=dubsum}
\[
 \sum_{k=1}^{b^{m-a}}\sum_{j=0}^{k-1}\ibra{k\geq j}p_b(b^{m-a}(n-1)+k-j)
 =
 \sum_{j=1}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)
\]

Finally by Corollary \ref{cor:fac+j}:
\begin{align*}
\sum_{j=1}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)
 & = \left({b^{m-a}\choose2}-{b^{m-a}-b+1\choose 2}\right)p_b(b^{m-a}(n-1))\\
 & \tab + \ibra{m>a+1}\sum_{j=b}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)\\
\end{align*}

Therefore
\begin{align*}
\sum_{k=1}^{b^{m-a}-1}p_b(b^{m-a+1}(n-1)+kb)
 & = (b^{m-a}-1)p_b(b^{m-a+1}(n-1)) + \sum_{k=1}^{b^{m-a}}kp_b(b^{m-a}n-k)\\
 & = (b^{m-a}-1)p_b(b^{m-a+1}(n-1))\\
 & \tab + \left({b^{m-a}\choose2}-{b^{m-a}-b+1\choose2}\right)p_b(b^{m-a}(n-1))\\
 & \tab + \ibra{m>a+1}\sum_{j=b}^{b^{m-a}-1}(b^{m-a}-j)p_b(b^{m-a}(n-1)+j)\\
\end{align*}
\end{proof}

The goal now is to evaluate the expression
\begin{align*}
\lhs
 & = p_b(b^m n)\\
 & = F^{b^{m-1}}(p_b(b^m n))\\
 & = p_b(b^m n - b^m) + \sum_{k=0}^{b^{m-1}-1}p_b(b^{m-1}n - k)\\
 & = p_b(b^m(n{-}1)) + \sum_{k=0}^{b^{m-1}-1}p_b(b^{m-1}n - k)\\
 & = p_b(b^m(n{-}1)) + \sum_{k=1}^{b^{m-1}}p_b(b^{m-1}(n-1) + k)\\
 & = p_b(b^m(n{-}1)) + p_b(b^{m-1}n) + \sum_{k=1}^{b-1}p_b(b^{m-1}(n-1)+k) + \ibra{m>2}\sum_{k=b}^{b^{m-1}-1}p_b(b^{m-1}(n-1)+k)\\
 & = p_b(b^m(n{-}1)) + p_b(b^{m-1}n) + (b-1)p_b(b^{m-1}(n-1)) + \ibra{m>2}\sum_{k=b}^{b^{m-1}-1}p_b(b^{m-1}(n-1)+k)\\
\end{align*}
 Note the last term is $0$ if $m\leq2$ thus the case $m=2$ is finished here.

The last term then becomes:
\begin{align*}
\lhs
 & = \sum_{k=b}^{b^{m-1}-1}p_b(b^{m-1}(n-1)+k)\\
 & = \sum_{k=b}^{b^{m-1}-1}p_b(b^{m-1}(n-1)+k)\\
 & = \sum_{u=1}^{b^{m-2}-1}\sum_{v=0}^{b-1}p_b(b^{m-1}(n-1)+ub+v)\\
 & = \sum_{u=1}^{b^{m-2}-1}\sum_{v=0}^{b-1}p_b(b^{m-1}(n-1)+ub)\\
 & = b\sum_{u=1}^{b^{m-2}-1}p_b(b^{m-1}(n-1)+ub)\\
 & = b\sum_{u=1}^{b^{m-2}-1}p_b(b^{m-1}(n-1)+ub)\\
\end{align*}

The expression of interest is now:
\begin{align*}
p_b(b^m n)
 & = p_b(b^m(n{-}1)) + p_b(b^{m-1}n) + (b-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b\sum_{u=1}^{b^{m-2}-1}p_b(b^{m-1}(n-1)+ub)\\
\end{align*}

Theorem \ref{thm:+kb} can be applied with $a=2$ to the last term. Then
\begin{align*}
\lhs
 & = \sum_{k=1}^{b^{m-2}-1}p_b(b^{m-1}(n-1)+kb)\\
 & = (b^{m-2}-1)p_b(b^{m-1}(n-1))\\
 & \tab + \left({b^{m-2}\choose2}-{b^{m-2}-b+1\choose2}\right)p_b(b^{m-2}(n-1))\\
 & \tab + \ibra{m>3}\sum_{j=b}^{b^{m-2}-1}(b^{m-2}-j)p_b(b^{m-2}(n-1)+j)\\
\end{align*}

Note the last term is 0 if $m\leq3$.
Thus the case $m=3$ is finished here (compare Theorem \ref{thm:m=3}).

The expression of interest is now:
\begin{align*}
p_b(b^m n)
 & = p_b(b^m(n{-}1)) + p_b(b^{m-1}n) + (b-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b\sum_{u=1}^{b^{m-2}-1}p_b(b^{m-1}(n-1)+ub)\\
 & = p_b(b^m(n{-}1)) + p_b(b^{m-1}n) + (b-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b(b^{m-2}-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b\left({b^{m-2}\choose2} - {b^{m-2}-b+1\choose 2}\right)p_b(b^{m-2}(n-1))\\
 & \tab + \ibra{m>3}b\sum_{j=b}^{b^{m-2}-1}(b^{m-2}-j)p_b(b^{m-2}(n-1)+j)\\
\end{align*}

Again, the action is in the last term:
\begin{align*}
\lhs
 & = \sum_{j=b}^{b^{m-2}-1}(b^{m-2}-j)p_b(b^{m-2}(n-1)+j)\\
 & = \sum_{u=1}^{b^{m-3}-1}\sum_{v=0}^{b-1}(b^{m-2}-ub-v)p_b(b^{m-2}(n-1)+ub+v)\\
 & = \sum_{u=1}^{b^{m-3}-1}\sum_{v=0}^{b-1}(b^{m-2}-ub-v)p_b(b^{m-2}(n-1)+ub)\\
 & = \sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)\sum_{v=0}^{b-1}(b^{m-2}-ub-v)\\
 & = \sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)\left((b^{m-2}-ub)b-\sum_{v=0}^{b-1}v\right)\\
 & = \sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)\left(b^2(b^{m-3}-u)-{b\choose2}\right)\\
 & = b^2\sum_{u=1}^{b^{m-3}-1}(b^{m-3}-u)p_b(b^{m-2}(n-1)+ub)
 - {b\choose2}\sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)\\
\end{align*}

\begin{comment}
\begin{align*}
 & = \sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)\sum_{v=0}^{b-1}(b^{m-2}-(u-1)b+b-v)\\
 & = \sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)\left(b^{m-2}-(u-1)b + \sum_{v=0}^{b-1}(b-v)\right)\\
 & = \sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)\left(b^{m-2}-(u-1)b + \sum_{v=1}^{b}v\right)\\
 & = \sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)\left(b^{m-2}-(u-1)b + {b+1 \choose 2}\right)\\
 & = {b+1 \choose 2}\sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)
        + \sum_{u=1}^{b^{m-3}-1}(b^{m-2}-(u-1)b)p_b(b^{m-2}(n-1)+ub)\\
 & = {b+1 \choose 2}\sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)
        + b\sum_{u=1}^{b^{m-3}-1}(b^{m-3}-(u-1))p_b(b^{m-2}(n-1)+ub)\\
 & = {b+1 \choose 2}\sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)
        + b\sum_{u=1}^{b^{m-3}-1}(b^{m-3}-u+1)p_b(b^{m-2}(n-1)+ub)\\
 & = {b+1 \choose 2}\sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)\\
 & \tab + b\sum_{u=1}^{b^{m-3}-1}(b^{m-3}-u)p_b(b^{m-2}(n-1)+ub)
        + b\sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)\\
 & = \left({b+1\choose2}+b\right)\sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)\\
 & \tab + b\sum_{u=1}^{b^{m-3}-1}(b^{m-3}-u)p_b(b^{m-2}(n-1)+ub)\\
\end{align*}
\end{comment}

Theorem \ref{thm:+kb} can be applied with $a=3$ to the second term. Then

\begin{align*}
\lhs
 & = \sum_{j=b}^{b^{m-2}-1}(b^{m-2}-j)p_b(b^{m-2}(n-1)+j)\\
 & = b^2\sum_{u=1}^{b^{m-3}-1}(b^{m-3}-u)p_b(b^{m-2}(n-1)+ub)
 - {b\choose2}\sum_{u=1}^{b^{m-3}-1}p_b(b^{m-2}(n-1)+ub)\\
 & = b^2\sum_{u=1}^{b^{m-3}-1}(b^{m-3}-u)p_b(b^{m-2}(n-1)+ub)\\
 & \tab - {b\choose2}(b^{m-3}-1)p_b(b^{m-2}(n-1))\\
 & \tab - {b\choose2}\left({b^{m-3}\choose2}-{b^{m-3}-b+1\choose2}\right)p_b(b^{m-3}n(n-1))\\
 & \tab - \ibra{m>4}{b\choose2}\sum_{j=b}^{b^{m-3}-1}(b^{m-3}-j)p_b(b^{m-3}(n-1)+j)\\
\end{align*}

The expression of interest is now:
\begin{align*}
p_b(b^m n)
 & = p_b(b^m(n{-}1)) + p_b(b^{m-1}n) + (b-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b(b^{m-2}-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b\left({b^{m-2}\choose2} - {b^{m-2}-b+1\choose 2}\right)p_b(b^{m-2}(n-1))\\
 & \tab + \ibra{m>3}b\sum_{j=b}^{b^{m-2}-1}(b^{m-2}-j)p_b(b^{m-2}(n-1)+j)\\
 & = p_b(b^m(n{-}1)) + p_b(b^{m-1}n) + (b-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b(b^{m-2}-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b\left({b^{m-2}\choose2} - {b^{m-2}-b+1\choose 2}\right)p_b(b^{m-2}(n-1))\\
 & \tab + \ibra{m>3}b^3\sum_{u=1}^{b^{m-3}-1}(b^{m-3}-u)p_b(b^{m-2}(n-1)+ub)\\
 & \tab - \ibra{m>3}b{b\choose2}(b^{m-3}-1)p_b(b^{m-2}n(n-1))\\
 & \tab - \ibra{m>3}b{b\choose2}\left({b^{m-3}\choose2}-{b^{m-3}-b+1\choose2}\right)p_b(b^{m-3}n(n-1))\\
 & \tab - \ibra{m>4}b{b\choose2}\sum_{j=b}^{b^{m-3}-1}(b^{m-3}-j)p_b(b^{m-3}(n-1)+j)\\
\end{align*}

known typos unfixed at or past this point involving the $b^3$ term above

Now consider the sum
\begin{align*}
\lhs
& = \sum_{k=1}^{b^{m-3}-1}(b^{m-3}-k)p_b(b^{m-2}(n-1)+kb)\\
& = \sum_{k=1}^{b^{m-3}-1}(b^{m-3}-k)\left(p_b(b^{m-2}(n-1)+(k-1)b)+p_b(b^{m-3}(n-1)+k)\right)\\
& = \sum_{k=1}^{b^{m-3}-1}(b^{m-3}-k)\biggl(\ibra{k\geq2}\left(p_b(b^{m-2}(n-1)+(k-2)b)+p_b(b^{m-3}(n-1)+k-1)\right)\\
& \tab + p_b(b^{m-3}(n-1)+k)\biggr)\\
& = \sum_{k=1}^{b^{m-3}-1}(b^{m-3}-k)\left(\ibra{k\geq2}p_b(b^{m-2}(n-1)+(k-2)b)+\sum_{j=0}^{1}p_b(b^{m-3}(n-1)+k-j)\right)\\
& = \sum_{k=1}^{b^{m-3}-1}(b^{m-3}-k)\left(p_b(b^{m-2}(n-1))+\sum_{j=0}^{k-1}p_b(b^{m-3}(n-1)+k-j)\right)\\
& = p_b(b^{m-2}(n-1))\sum_{k=1}^{b^{m-3}-1}(b^{m-3}-k) \text{ let $j = b^{m-3}-k$ in this sum }\\
& \tab + \sum_{k=1}^{b^{m-3}-1}(b^{m-3}-k)\sum_{j=0}^{k-1}p_b(b^{m-3}(n-1)+k-j)\\
& = p_b(b^{m-2}(n-1))\sum_{j=1}^{b^{m-3}-1}j + \sum_{k=1}^{b^{m-3}-1}(b^{m-3}-k)\sum_{j=0}^{k-1}p_b(b^{m-3}(n-1)+k-j)\\
& = {b^{m-3} \choose 2} p_b(b^{m-2}(n-1))
       + \sum_{k=1}^{b^{m-3}-1}(b^{m-3}-k)\sum_{j=0}^{k-1}p_b(b^{m-3}(n-1)+k-j) \text{ let $u = k-j$}\\
& = {b^{m-3} \choose 2} p_b(b^{m-2}(n-1))
       + \sum_{k=1}^{b^{m-3}-1}\sum_{u=1}^{k}(b^{m-3}-k)p_b(b^{m-3}(n-1)+u) \text{ let $u = j$}\\
& = {b^{m-3} \choose 2} p_b(b^{m-2}(n-1))
       + \sum_{k=1}^{b^{m-3}-1}\sum_{j=1}^{k}(b^{m-3}-k)p_b(b^{m-3}(n-1)+j)\\
\end{align*}

The expression of interest is now:
\begin{align*}
p_b(b^m n)
 & = p_b(b^m(n{-}1)) + p_b(b^{m-1}n) + (b-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b(b^{m-2}-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b\left({b^{m-2}\choose2} - {b^{m-2}-b+1\choose 2}\right)p_b(b^{m-2}(n-1))\\
 & \tab + \ibra{m>3}b^3\sum_{u=1}^{b^{m-3}-1}(b^{m-3}-u)p_b(b^{m-2}(n-1)+ub)\\
 & \tab - \ibra{m>3}b{b\choose2}(b^{m-3}-1)p_b(b^{m-2}n(n-1))\\
 & \tab - \ibra{m>3}b{b\choose2}\left({b^{m-3}\choose2}-{b^{m-3}-b+1\choose2}\right)p_b(b^{m-3}n(n-1))\\
 & \tab - \ibra{m>4}b{b\choose2}\sum_{j=b}^{b^{m-3}-1}(b^{m-3}-j)p_b(b^{m-3}(n-1)+j)\\
 & = p_b(b^m(n{-}1)) + p_b(b^{m-1}n) + (b-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b(b^{m-2}-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b\left({b^{m-2}\choose2} - {b^{m-2}-b+1\choose 2}\right)p_b(b^{m-2}(n-1))\\
 & \tab + \ibra{m>3}b^3{b^{m-3} \choose 2} p_b(b^{m-2}(n-1))\\
 & \tab + \ibra{m>3}b^3\sum_{k=1}^{b^{m-3}-1}\sum_{j=1}^{k}(b^{m-3}-k)p_b(b^{m-3}(n-1)+j)\\
 & \tab - \ibra{m>3}b{b\choose2}(b^{m-3}-1)p_b(b^{m-2}n(n-1))\\
 & \tab - \ibra{m>3}b{b\choose2}\left({b^{m-3}\choose2}-{b^{m-3}-b+1\choose2}\right)p_b(b^{m-3}n(n-1))\\
 & \tab - \ibra{m>4}b{b\choose2}\sum_{j=b}^{b^{m-3}-1}(b^{m-3}-j)p_b(b^{m-3}(n-1)+j)\\
\end{align*}

Now consider the sum
\begin{align*}
\lhs
 & = \sum_{k=1}^{b^{m-3}-1}\sum_{j=1}^{k}(b^{m-3}-k)p_b(b^{m-3}(n-1)+j)\\
 & = \sum_{k=1}^{b^{m-3}-1}\sum_{j=1}^{k}\ibra{1\leq j\leq k}(b^{m-3}-k)p_b(b^{m-3}(n-1)+j)\\
 & = \sum_{k=1}^{b^{m-3}-1}\sum_{j=1}^{b^{m-3}-1}\ibra{1\leq j\leq k}(b^{m-3}-k)p_b(b^{m-3}(n-1)+j)\\
 & = \sum_{j=1}^{b^{m-3}-1}\sum_{k=1}^{b^{m-3}-1}\ibra{1\leq j\leq k}(b^{m-3}-k)p_b(b^{m-3}(n-1)+j)\\
 & = \sum_{j=1}^{b^{m-3}-1}p_b(b^{m-3}(n-1)+j)\sum_{k=1}^{b^{m-3}-1}\ibra{1\leq j\leq k}(b^{m-3}-k)\\
 & = \sum_{j=1}^{b^{m-3}-1}p_b(b^{m-3}(n-1)+j)\sum_{k=j}^{b^{m-3}-1}(b^{m-3}-k)\text{ let $u=b^{m-3}-k$}\\
 & = \sum_{j=1}^{b^{m-3}-1}p_b(b^{m-3}(n-1)+j)\sum_{u=1}^{b^{m-3}-j}u\\
 & = \sum_{j=1}^{b^{m-3}-1}p_b(b^{m-3}(n-1)+j){b^{m-3}-j+1\choose2}\\
 & = \sum_{j=1}^{b^{m-3}-1}{b^{m-3}-j+1\choose2}p_b(b^{m-3}(n-1)+j)\\
 & = \sum_{j=1}^{b-1}{b^{m-3}-j+1\choose2}p_b(b^{m-3}(n-1)+j)\\
 & \tab + \ibra{m>4}\sum_{j=b}^{b^{m-3}-1}{b^{m-3}-j+1\choose2}p_b(b^{m-3}(n-1)+j)\\
\end{align*}

Focusing on the first sum
\begin{align*}
\sum_{j=1}^{b-1}{b^{m-3}-j+1\choose2}p_b(b^{m-3}(n-1)+j)
 & = \sum_{j=1}^{b-1}{b^{m-3}-j+1\choose2}p_b(b^{m-3}(n-1))\\
 & = p_b(b^{m-3}(n-1))\sum_{j=1}^{b-1}{b^{m-3}-j+1\choose2}\text{ let $k=b^{m-3}-j+1$}\\
 & = p_b(b^{m-3}(n-1))\sum_{k=b^{m-3}-b+2}^{b^{m-3}}{k\choose2}\\
 & = p_b(b^{m-3}(n-1))\left({b^{m-3}+1\choose3}-{b^{m-3}-b+2\choose3}\right)\\
 & = \left({b^{m-3}+1\choose3}-{b^{m-3}-b+2\choose3}\right)p_b(b^{m-3}(n-1))\\
\end{align*}

Therefore
\begin{align*}
\sum_{k=1}^{b^{m-3}-1}\sum_{j=1}^{k}(b^{m-3}-k)p_b(b^{m-3}(n-1)+j)
 & = \left({b^{m-3}+1\choose3}-{b^{m-3}-b+2\choose3}\right)p_b(b^{m-3}(n-1))\\
 & \tab + \ibra{m>4}\sum_{j=b}^{b^{m-3}-1}{b^{m-3}-j+1\choose2}p_b(b^{m-3}(n-1)+j)\\
\end{align*}

The expression of interest is now:
\begin{align*}
p_b(b^m n)
 & = p_b(b^m(n{-}1)) + p_b(b^{m-1}n) + (b-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b(b^{m-2}-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b\left({b^{m-2}\choose2} - {b^{m-2}-b+1\choose 2}\right)p_b(b^{m-2}(n-1))\\
 & \tab + \ibra{m>3}b^3{b^{m-3} \choose 2} p_b(b^{m-2}(n-1))\\
 & \tab + \ibra{m>3}b^3\sum_{k=1}^{b^{m-3}-1}\sum_{j=1}^{k}(b^{m-3}-k)p_b(b^{m-3}(n-1)+j)\\
 & \tab - \ibra{m>3}b{b\choose2}(b^{m-3}-1)p_b(b^{m-2}n(n-1))\\
 & \tab - \ibra{m>3}b{b\choose2}\left({b^{m-3}\choose2}-{b^{m-3}-b+1\choose2}\right)p_b(b^{m-3}n(n-1))\\
 & \tab - \ibra{m>4}b{b\choose2}\sum_{j=b}^{b^{m-3}-1}(b^{m-3}-j)p_b(b^{m-3}(n-1)+j)\\
 & = p_b(b^m(n{-}1)) + p_b(b^{m-1}n) + (b-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b(b^{m-2}-1)p_b(b^{m-1}(n-1))\\
 & \tab + \ibra{m>2}b\left({b^{m-2}\choose2} - {b^{m-2}-b+1\choose 2}\right)p_b(b^{m-2}(n-1))\\
 & \tab + \ibra{m>3}b^3{b^{m-3} \choose 2} p_b(b^{m-2}(n-1))\\
 & \tab + \ibra{m>3}b^3\left({b^{m-3}+1\choose3}-{b^{m-3}-b+2\choose3}+X\right)p_b(b^{m-3}(n-1))\\
 & \tab - \ibra{m>3}b{b\choose2}(b^{m-3}-1)p_b(b^{m-2}n(n-1))\\
 & \tab - \ibra{m>3}b{b\choose2}\left({b^{m-3}\choose2}-{b^{m-3}-b+1\choose2}\right)p_b(b^{m-3}n(n-1))\\
 & \tab - \ibra{m>4}b{b\choose2}\sum_{j=b}^{b^{m-3}-1}(b^{m-3}-j)p_b(b^{m-3}(n-1)+j)\\
 & \tab + \ibra{m>4}b^3\sum_{j=b}^{b^{m-3}-1}{b^{m-3}-j+1\choose2}p_b(b^{m-3}(n-1)+j)\\
\end{align*}

And the case $m=4$ is done here, except for the mystery term of $X = {b-1\choose3}/2$.
This term probably represents a typo in the (currently 8 page) argument.

\pagebreak
\begin{sideways}
\begin{minipage}{\textheight}
\[
\begin{array}{llllll}
m & b=2 & b=3 & b=4 & b=5\\
3
 & 1 + 6q + q^2
 & 1 + 19q + 7q^2
 & 1 + 42q + 21q^2
 & 1 + 78q + 46q^2\\
4
 & 1 + 31q + 31q^2 + q^3
 & 1 + 234q + 447q^2 + 47q^3
 & 1 + 1081q + 2635q^2 + 379q^3
 & 1 + 3072q + 10218q^2 + 1704q^3\\
% & 1 + 10335*q + 30735*q^2 + 5585*q^3\\
% & 1 + 24896*q + 77801*q^2 + 14951*q^3\\
% & 1 + 53669*q + 173747*q^2 + 34727*q^3\\
5
 & 1 + 196q+ 630q^2 + 196q^2 + q^4
 & 1 + 5822q + 33504q^2 + 19040q^3 + 682q^4\\
\end{array}
\]
\end{minipage}
\end{sideways}
\pagebreak

\end{document}
