# Tag Info

I started your problem from scratch and arrived to something different (I have not been able to find where there has been a difference). First, I arrived to $$A(z)=\frac{-616 z^5+1540 z^4-1198 z^3+267 z^2+55 z-23}{(z-1)^2 (2 z-1)^3 (4 z+1)}$$ which decomposes as $$A(z)=-\frac{19}{z-1}-\frac{2}{(1-2 z)^2}+\frac{5}{(z-1)^2}-\frac{2}{(2 z-1)^3}-\frac{1}{4 ... 2 We count the number of bad n-sequences, the ones that have 3 consecutive A somewhere. Let this number be b(n). We can make a bad sequence of length n+1 in two ways: (i) append A or B to a bad sequence of length n or (ii) append AAA to a good sequence of length n-2. Thus$$b(n+1)=2b(n)+a(n-2).$$In terms of a(n), we have ... 2 Oh it's a 'trick' question. Note that the characteristic polynomial of the corresponding homogenous recurrence is r \mapsto r^3-12r-16 which has 4 as a root, and hence when you substituted 4^n in it didn't work. In general we can solve all such recurrences by repeatedly applying the operator f(n) \mapsto f(n+1) - r f(n) for some r until ... 1 I see user21820 has given a good answer while I went AFK, but I figured I'd share this anyway since I worked it out... We can apply the method of annihilators to convert this into a 6th order, constant coefficient, homogeneous recurrence. For background on the method of annihilators, see these links. First, we rewrite and reindex the recurrence:$$a_n = ...
Go for generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, rewrite the recurrence without index subtractions: $$a_{n + 3} = 12 a_{n + 1} + 16 a_n + 576 \cdot 4^n + 81 n + 243$$ Multiply by $z^n$, sum over $n \ge 0$, and recognize a few sums to get: $$\frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3} = 12 \frac{A(z) - a_0}{z} + 16 A(z) + 576 ... 1 Unless you give some more initial terms, it is not possible to find f(n) where n is not a power of 2. When n = 2^k, I claim that f(2^k) = k+1 for k \ge 1. This is true for f(2) so assume it holds for some k = j > 1. Then f(2^{j+1}) = f(2^j)+1 = j+2 so we are done. 1 A simpler way to set this kind of problems up is to write the recurrence with no subtraction in indices:$$ g_{n + 2} = g_{n + 1} + g_n + n + 2 Multiply by x^n, sum over n \ge 0, and recognize: \begin{align} \sum_{n \ge 0} a_{n + k} x^k &= \frac{G(x) - g_0 - g_1 z - \ldots - g_{k - 1} x^{k - 1}}{x^k} \\ \sum_{n \ge 0} x^n &= \frac{1}{1 - ... 1 The characteristic polynomial \lambda^3-12\lambda +16 of the corresponding homogeneous difference equationh_n-12 h_{n-2}+16 h_{n-3}=0\tag{1}$$has 2, 2, -4 as roots. The general solution of (1) is therefore given by$$h_n=(A+Bn) 2^n+ C(-4)^n$$with arbitrary A, B, C. On the right hand side of the given difference equation$$g_n-12 ...