# Tag Info

## Hot answers tagged recurrence-relations

4

This is the Stern-Brocot tree, which is bijective to the positive rationals.

2

$\def\w{\text{weight}} \def\C{\mathcal{C}}$ Here is the solution using the cluster method. The generating function is $$f(s)=\frac1{1-4s-\w(\C)},$$ so we need to find $\w(\C)$. The set of bad words is $\{ab,ba\}$. Proceeding as in the paper, we get $$\w(\C[ab])=-s^2-s\cdot \w(C[ba])\\ \w(\C[ba]) = -s^2-s\cdot \w(C[ab])$$ Furthermore, $\w(\C)=\w(\C[ab])+... 2 I do not know about the Goulden-Cluster method, but I can explain why$a_n\neq 4a_{n-1}-2a_{n-2}$. Let us call the strings counted by$4a_{n-1}$type I, and the strings counted by$2a_{n-2}$type II. That is, Type I: (valid string of length$n-1$) + (any single letter) Type II: (valid string of length$n-2$) + ($ab$or$ba$) The subtraction$4a_{n-1}-2a_{...

1

Claude Leibovici's method is good, but if you want the generating function, you basically found it already. Just solve the equation, $$F(x) - 2 = 3x F(x) + \frac{x}{1-x} \implies F(x) = \frac{2-x}{(1-x)(1-3x)} .$$ (At this point you instead seem to have substituted $F(x) = \frac{1}{1-x}$ in your working, which was wrong). Now, if we want to extract ...

1

Hint To solve $$a_{n} = 3a_{n-1} + 1$$ since the problem is the constant, let $a_n=b_n+k$ and replace $$b_n+k=3b_{n-1}+3k+1$$ So, make $$k=3k+1\implies k=-\frac 12\implies b_n= 3b_{n-1}$$ which is simple

1

You are almost there. Now try to do $L_i \leftarrow L_i-L_{n+1}$ for all $1\leq i \leq n$. Where $L_i$ denotes the $i$-th row. By substracting the rows you will have the opportunity to make the missing factors appear as you did with the columns, and you will end up with only $0$s in the last column except at the bottom. Indeed, for all $1\leq i,j \leq n$ you ...

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