Hidden underneath the "annihilator" concept in linear recurrences is the notion of power series and generator functions.
If you have a sequence $\{a_n\}$ you can define the power series:
$$a(z) = \sum_{n=0}^\infty a_n z^n$$
The abstract algebra part is that we are dealing here with a "formal power series" - we don't need to have it converge for any $z$. Given two power series, $a(z)$ and $b(z)$, we can multiply them to get a new power series, for example. We can add power series.
Now given your $a_n=f(n)$, we can see that:
$$(1-4z)a(z) = a_0 + \sum_{n=1}^\infty (a_n-4a_{n-1})z^n = a_0$$
We then define $E(a(z)) = \frac{a(z)-a(0)}{z}$. This takes a power series and shifts it one to the left. Thn we see that:
$$\frac{a(z)-a(0)}{z} - 4a(z) = 0$$
Thus we get $(E-4)(a(z)) = 0$.
Working backwards, we also see that $a(z)=\frac{a_0}{1-4z}=a(z)$. But we know that we can expand $\frac{1}{1-4z} =\sum_{n} 4^nz^n$. So we get that $a_n = 4^na_0 z^n$.
That might look like I've played a little slight of hand, since how can I show $\frac{1}{1-4z} = \sum_{n} 4^nz^n$ without worrying about convergence? That's the magic of power series - they form a commutative ring, and we can work out multiplicative inverses for (some) elements in this ring. Two power series are considered equal if they have the same coefficients, and there are no zero divisors, so it just magically falls out.
More generally, if $R(E)$ is some polynomial of $E$ and $f$ satisfies the condition $R(E)f = 0$ then when we define $f(z)=\sum f(n)z^n$ we get a rather complicated expression but which ultimately boils down to some $q(z)f(z) = p(z)$ where $q(z)$ and $p(z)$ are always (finite) polynomials, not power series. So we get $f(z)=\dfrac{p(z)}{q(z)}$. We can expand that by representing $p(z)/q(z)$ in terms of partial fractions.
Note, if $a(z)=\sum a_nz^n$ then $$(E^k)(a(z)) =\frac{a(z)-a_0-a_1z-\dots a_{k-1}z^{k-1}}{z^k}$$
Note: At first I'll try to describe some key ideas of the repertoire method using a (very) simple example. This should give you some basic information about this method. But to get a good impression what's really going on, we will also look at a considerably more complex example.
Repertoire method (some basics)
This method is based upon two essential ingredients. The first one is the possibility to build linear combinations of already known recurrences.
Let's assume we have a recurrence for $x_n$
\begin{align*}
x_0&=a_0\\
x_n&=a_n+x_{n-1},\quad n>0
\end{align*}
and we have another recurrence for $y_n$
\begin{align*}
y_0&=b_0\\
y_n&=b_n+y_{n-1},\quad n>0
\end{align*}
Then provided these recurrences are known, we also know by linearity that an equation with additive term
$$\alpha a_n+\beta b_n$$
will have the solution
$$\alpha x_n + \beta y_n$$
To make it more concrete, let $a_n=3$ and $b_n=5n^2+1$. Assuming we know the solutions $x_n$ and $y_n$ of the recurrences
\begin{align*}
x_0&=3&y_0&=1\\
x_n&=3+x_{n-1},\quad n>0&y_n&=5n^2+1+y_{n-1},\quad n>0
\end{align*}
then we also know by linearity that the solution of the recurrence
\begin{align*}
z_0&=7\\
z_n&=2n^2+7+z_{n-1}
\end{align*}
is
\begin{align*}
z_n=\frac{11}{5}x_n+\frac{2}{5}y_n
\end{align*}
We observe that in this case we have a repertoire of two solutions $x_n$ and $y_n$ which we can linearly combine in order to find the wanted solution $z_n$.
BUT: We typically start with a recurrence $z_n$ without having a repertoire of proper candidates. And this will be the second ingredient. We have to build a repertoire.
The second ingredient is building a repertoire which can be used for linear combinations. Let's assume we start with a recurrence
\begin{align*}
z_0&=7\\
z_n&=2n^2+7+z_{n-1},\quad n>0\tag{1}
\end{align*}
So, if we try to solve this recurrence by the method of repertoire, we first generalise the recurrence and consider instead
\begin{align*}
\mathcal{Z}_0&=a_0\\
\mathcal{Z}_n&=a_n+\mathcal{Z}_{n-1},\quad n>0
\end{align*}
Now it's time for some creative ideas which is typically the most challenging phase when using this method. We want to find a repertoire consisting of two members. One of them with $a_n=const.$ and the other with $a_n=$ square of $n$. In order to do so we have to guess some proper candidates for $\mathcal{Z}_n$ which provides us with the wanted $a_n$.
So let's guess a first candidate. This is not too hard (in this case) since setting $\mathcal{Z}_n=n$ gives
\begin{align*}
a_0&=0\\
n&=a_n+n-1\quad n>0
\end{align*}
and we find: $a_0=0$ and $a_n=1,n>0$.
We get the first candidate, let's say $x_n$ with
\begin{align*}
x_0&=0\\
x_n&=1+x_{n-1},\quad n>0\tag{2}
\end{align*}
We can similarly find a proper second candidate which provides us with $a_n=$ square of $n$ by observing that typically the sum of $k-th$ powers of natural numbers is something with a $(k+1)$-th power. So we guess $\mathcal{Z}_n=n^3$ which gives
\begin{align*}
a_0&=0\\
n^3&=a_n+(n-1)^3\quad n>0
\end{align*}
and we find $a_0=0$ and $a_n=3n^2-3n+1,n>0$.
We get the second candiate, let's say $y_n$ with
\begin{align*}
y_0&=0\\
y_n&=3n^2-3n+1+y_{n-1},\quad n>0\tag{3}
\end{align*}
We observe that $y_n$ also contains a linear term in $n$ which is not wanted, since we need according to (1) $a_n=n^2+7$. So we extend our repertoire by introducing a third member which provides us with $a_n=$ linear term in $n$. Then we should be able to eliminate the linear term in $n$ by a proper linear combination of the three members. We guess $\mathcal{Z}_n=n^2$ which gives
\begin{align*}
a_0&=0\\
n^2&=a_n+(n-1)^2\quad n>0
\end{align*}
and we find $a_0=0$ and $a_n=2n-1,n>0$.
So we get the third candiate, let's say $u_n$ with
\begin{align*}
u_0&=0\\
u_n&=2n-1+u_{n-1},\quad n>0\tag{4}
\end{align*}
Let's have a look at the repertoire:
Overview of the three candidates
\begin{array}{rlcr}
\mathcal{Z}_n&&a_n&\\
\hline\\
x_n=&n\qquad&1&\qquad\qquad\text{acc. to }(2)\\
y_n=&n^3\qquad&3n^2-3n+1&\qquad\qquad\text{acc. to }(3)\\
u_n=&n^2\qquad&2n-1&\qquad\qquad\text{acc. to }(4)\\
\end{array}
We observe when using an appropriate linear combination
\begin{align*}
a_n&=2n^2+7\\
&=\frac{2}{3}\left(3n^2-3n+1\right)+\left(2n-1\right)+\frac{22}{3}
\end{align*}
and we conclude
\begin{align*}
z_n&=\frac{22}{3}x_n+\frac{2}{3}y_n+u_n+c_0\\
&=\frac{1}{3}n\left(2n^2+3n+22\right)+c_0
\end{align*}
Observe, that we have to determine a constant $c_0$ since we also have to properly respect the initial condition $z_0=7$. We do so by setting $c_0=7$ and so we finally get:
$$z_n=\frac{1}{3}n\left(2n^2+3n+22\right)+7,\quad n\geq 0$$
Let's summarise
Summary of the method by Repertoire
In order to solve a recurrence of the form
\begin{align*}
x_n=f(n)+g(x_{n-1},x_{n-2},\ldots,x_0)\tag{5}
\end{align*}
- we identify building blocks $f_1(n),\ldots,f_k(n)$ of $f(n)$, so that they can be linearly combined in order to form $f(n)$
\begin{align*}
f(n)=\lambda_1 f_1(n)+\ldots+\lambda_k f_k(n)
\end{align*}
then we consider the generalised representation of (5) by substituting $f(n)$ with $a_n$.
\begin{align*}
\mathcal{Z}_n=a_n+g(\mathcal{Z}_{n-1},\mathcal{Z}_{n-2},\ldots,\mathcal{Z}_0)
\end{align*}
and solve the simpler recurrences
\begin{align*}
x_n^{(l)}=f_l(n)+g(x_{n-1},x_{n-2},\ldots,x_0)\quad 1 \leq l \leq k
\end{align*}
by proper guessing of $x_n^{(l)}$ in order to get $f_l(n)$.
The solutions $x_n^{(l)}$ with $1\leq l \leq k$ form the repertoire of the method in order to solve $x_n$.
Determine the linear combination
$$f(n)=\lambda_1 f_1(n)+\ldots+\lambda_k f_k(n)$$
and deduce the solution
$$x_n=\lambda_1 x_n^{(1)}+\ldots+\lambda_k x_n^{(k)}+c_0$$
- Finally determine $c_0$ according to initial conditions
Note: There may be more than one initial condition which are to determine
Note: It may be necessary to extend the repertoire in order to remove unwanted terms which additionally occur during the calculation of the $x_n^{(l)}$.
What follows is no longer a core part of the answer. But if you are curious ... :-)
Note: You may object that the example above uses quite a heavy machinery for a simple recurrence. But this was only for demonstration.
A real life application is presented by D.E.Knuth and D.H.Greene in their Mathematics for the Analysis of Algorithms section 2.1.2.2. Albeit this example is somewhat lengthy, I can't resist to present at least the essential steps, since it's instructive to see the method in action.
Real life application of method by Repertoire: from D.E.Knuth and D.H.Greene
The sorting algorithm median-of-three quicksort leads to the following recurrence.
\begin{align*}
x_n=n+1+\frac{1}{\binom{n}{3}}\sum_{1\leq k \leq n}(k-1)(n-k)\left(x_{k-1}+x_{n-k}\right)
\end{align*}
At first we observe that the sum is symmetric and we replace the additive term $n+1$ by $a_n$ in preparation for the repertoire approach:
\begin{align*}
x_n=a_n+\frac{2}{\binom{n}{3}}\sum_{1< k <n}(k-1)(n-k)x_{k-1}
\end{align*}
First step: Create a Repertoire
We choose $x_n$ equal to the falling factorial $(n-1)^{\underline{s}}=(n-1)(n-2)\cdot\ldots\cdot(n-s)$
$$x_n=(n-1)^{\underline{s}}$$
and get
\begin{align*}
(n-1)^{\underline{s}}&=a_n+\frac{12}{n^{\underline{3}}}\sum_{1< k <n}(n-k)(k-1)^{\underline{s+1}}\\
&=\ldots\\
&=a_n+\frac{12(s+1)!}{n^{\underline{3}}}\binom{n}{s+3}
\end{align*}
This yields
\begin{align*}
a_n=(n-1)^{\underline{s}}-\frac{12}{(s+2)(s+3)}(n-3)^{\underline{s}}
\end{align*}
which is a family of solutions for the repertoire parametrised with $s$.
We observe:
\begin{array}{ccc}
&x_n&a_n\\
\hline\\
s=0\qquad&1&\qquad-1\\
s=1\qquad&(n-1)&\qquad2\\
s=2\qquad&(n-1)(n-2)&\qquad\frac{1}{5}\left(2n^2+6n-26\right)
\end{array}
Attention: Regrettably this family is inadequate; it lacks a member with linear $a_n$. You might want to read section 2.1.2.2 which clarifies why this lack is not surprising (:-))! But we have at least with $s=0$ a candidate for a constant amount.
Second step: Extend the repertoire
Since these types of algorithms are of order $O(n \log n)$ we introduce the Harmonic numbers $H_n=\sum_{k=1}^n\frac{1}{k}$ which contributes $O(\log n)$ and consider a new family
$$x_n=(n-1)^{\underline{t}}H_n$$
Solving for $a_n$ yields
\begin{align*}
(n-1)^{\underline{t}}H_n&=a_n+\frac{12}{n^{\underline{3}}}\sum_{1< k <n}(n-k)(k-1)^{\underline{t+1}}H_{k-1}\\
&=\ldots\\
&=a_n+\frac{12}{n^{\underline{3}}}\left(\frac{n^{\underline{t+3}}}{t+2}\left(H_{n-1}-\frac{1}{t+2}\right)\right.\\
&\qquad\qquad-\left.\frac{n^{\underline{t+3}}}{t+3}\left(H_n-\frac{1}{t+3}\right)+\frac{(n-1)^{\underline{t+2}}}{t+2}\right)
\end{align*}
The calculation above were done using the identity:
$$\sum_{k=1}^{n}\binom{k}{m}H_k=\binom{n+1}{m+1}\left(H_{n+1}-\frac{1}{m+1}\right)$$
Some simplifications lead to
\begin{align*}
a_n=H_n\left((n-1)^{\underline{t}}-\frac{12}{(t+2)(t+3)}(n-3)^{\underline{t}}\right)+\frac{12(2t+5)}{(t+2)^2(t+3)^2}(n-3)^{\underline{t}}
\end{align*}
(... The following text is nearly verbatim from the book ...)
Now when examining the small members of the family of solutions we discover a fortunate alignment:
\begin{array}{ccc}
&x_n&a_n\\
\hline\\
t=0\qquad&H_n&\qquad-H_n+\frac{5}{3}\\
t=1\qquad&(n-1)H_n&\qquad2H_n+\frac{7}{12}(n-3)\\
\end{array}
The smallest two solutions for $a_n$ both have leading term $H_n$. By an appropriate linear combination we can eliminate $H_n$ and obtain an $a_n$ that grows as order $n$:
$$x_n=(n+1)H_n\qquad\longleftrightarrow\qquad a_n=\frac{7n+19}{12}$$
The $s=0$ solution from the first family is used to adjust the constant term, enabling us to reconstruct the $a_n$ given in the original problem:
\begin{align*}
x_n=\frac{12}{7}\left((n+1)H_n+1\right)\qquad\longleftrightarrow\qquad a_n=n+1\tag{6}
\end{align*}
Third step: Adjustment for initial values
This solution for $x_n$ may not agree with the inital values $x_1$ and $x_2$. To accommodate arbitrary initial values we need to discover two extra degrees of freedom in the solution.
One degree of freedom can be observed in the first family of solutions. Combining $s=0$ with $s=1$ yields
$$x_n=n+1\qquad\longleftrightarrow\qquad a_n=0$$
So any multiple of $n+1$ can be added to the solution in (6).
The second degree of freedom is not quite so obvious. Since $a_n=0$ we have a simplified recurrence for $x_n$,
\begin{align*}
n(n-1)(n-2)x_n=12\sum_{1<k<n}(n-k)(k-1)x_{k-1}\tag{7}
\end{align*}
Using a generating function, $G(z)$, for the sequence $x_n$, the convolution on the right of (7) is represented by the product $\frac{1}{(1-z)^2}$ corresponding to $(n-k)$ and $G^{\prime}(z)$ corresponding to $(k-1)x_{k-1}$. We obtain the differential equation
$$G^{\prime\prime\prime}(z)=\frac{12}{(1-z)^2}G^{\prime}(z)$$
The nature of the equation suggests a solution of the form $G(z)=(1-z)^\alpha$, and testing this solution yields $\alpha=-2$ or $5$. The case $\alpha=-2$ corresponds to the previous observation that multiples of $n+1$ do not affect the solution. But for $\alpha =5$ we obtain an unusual solution that is zero after its first five values:
$$x_1=-5,\quad x_2=10,\quad x_3=-10,\quad x_4=5,\quad x_5=-1$$
This provides a second degree of freedom and yields the final solution
$$x_n=\frac{12}{7}\left((n+1)H_n+1\right)+c_1(n+1)+c_2(-1)^n\binom{5}{n}$$
where $c_1$ and $c_2$ are determined by the initial conditions.
Conclusion: It's instructive to see which candidates were selected for the repertoire in the first step. And it's very instructive to see how to cope with the inadequacy of the first family and select $x_n=(n-1)^{\underline{t}}H_n$ to extend the repertoire. But the last step indicates (at least for me) that finding a solution is also an art based upon a high level of creativity and a high level of experience.
Best Answer
Other answers build a summation and it isn't necessary. Here is a solution exclusively using the repertoire method and in the same spirit as 1.18 in the book
Let $$g(n)=A(n)α+B(n)γ+C(n)β_0+D(n)β_1 $$
Recall that $(\alpha, \gamma, \beta_0, \beta_1) \to (\alpha, 0, \beta_0, \beta_1)$ for $n = (b_mb_{m−1}...b_1b_0)_2$ is the radix changing solution $$A(n)α+C(n)β_0+D(n)β_1=(αβ_{b_{m−1}}...β_{b_1}β_{b_0})_3 \tag{1}$$
Let $(\alpha, \gamma, \beta_0, \beta_1) \to (0, 0, 0, 1)$. Then $$D(n) = (β_{b_{m−1}}...β_{b_1}β_{b_0})_3 = (b_{m−1}...b_1b_0)_3 \tag{2}$$
Think of $\beta_0 = 0$ and $\beta_1= 1$ as a function from radix-2 to radix-3, changing every power and preserving the coefficients.
Let $(\alpha, \gamma, \beta_0, \beta_1) \to (1, 0, 0, 0)$. Then $$ A(n) = (100...0)_3 = 3^m \tag{3}$$
Given the identity derived from $g(n)=n$, we can solve $$ A(n)−B(n)+D(n)=n$$ for $\gamma B(n)$. Thus plugging $$ \gamma B(n) = \gamma A(n) + \gamma D(n) - \gamma n$$ into (1), $$ A(n)α+ \gamma B(n)+ C(n)β_0+D(n)β_1=(αβ_{b_{m−1}}...β_{b_1}β_{b_0})_3 + \gamma A(n) + \gamma D(n) - \gamma n $$
Finally, for $n = (b_mb_{m−1}...b_1b_0)_2$, we can plug in (3) and (2), $$ g(n) = (αβ_{b_{m−1}}...β_{b_1}β_{b_0})_3 + \gamma(1b_{m−1}...b_1b_0)_3 - \gamma (b_mb_{m−1}...b_1b_0)_2 $$