Tag Info

Hot answers tagged

3

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 = ...


1

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 equation $$h_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 ...



Only top voted, non community-wiki answers of a minimum length are eligible