Suppose $f(n)$ is the number of strings of length $n$ with symbols from the alphabet $\{a,b,c,d\}$ with an even number of $a$’s.
(b) Show that $f$ satisfies the recurrence $f(n+1)=2f(n)+4^n$
My approach was to first to assume the case holds for $n=k$ and then consider the case for $n=k+1$(It is easy to show that it holds for the base case). I first considered the case for where strings have $a$ NOT as the last element. Then the strings with the previous sequence of elements (same strings from strings with length $k+1$ but without the last element ) have even $a$'s which means that there are $f(k)$ strings with length $k$. The last element can be $b,c,d$, so there are $3f(k)$ strings with length $k+1$ with $a$ NOT as the last element.
Now, the problem is that I am not sure if this method works for the case where the last element IS an a. also, are there any other ways to prove this? It seems to me that my approach lacks rigor.
Your approach is quite right, and I believe its level of rigor fits the question.
As you correctly said, considering all possible strings of length $n+1$ with that property yields a partition in two sets: chopping off the last letter, we can either end up with a string of length $n$ which already has an even number of $a$, or we do not and the string has an odd number of $a$ - so we must have chopped off an $a$. So the question boils down to whether or not the string ends with an $a$.
The number of strings of the first kind, as you noted, is $3f(n)$ since the last letter can be $b, c, d$. The number of strings of the second kind is the exact same as the number of strings of length $n$ that do not contain an even number of $a$, since we know we chopped off one. And we can find this number by considering all possible strings of length $n$ and then subtracting the number of those that do have an even number of $a$: $4^n - f(n)$. This works because a string can either contain an even or an odd number of $a$, no in-between.
So putting it all together yields: $$f(n+1)= 3f(n) + (4^n - f(n)) = 2f(n) + 4^n$$