Hi I don't know where to start to solve this reccurence relation:
$g(1)=2$
$ g(2n)=3g(n)+1$
$ g(2n+1)=3g(n)-2$
of coures I can make it:
$ g(1)=2$
$ g(n)=g(2n)/3-1/3$
$ g(n)=g(2n+1)/3-2/3$
but does it make any sense?
can you give me a clue or link where I could read about solving these kind of relations?
Let $h(n)=g(n)+\frac12$. then $$h(2n)=g(2n)+\frac12=3g(n)+\frac12+1=3h(n)$$ and $$ h(2n+1)=g(2n+1)+\frac12=3g(n)-\frac32=3 h(n)-3.$$ This recursion reminds suspiciously of the write-in-binary-read-in-ternary function $f$ defined by the recursion $f(1)=1$, $f(2n)=3f(n)$, $f(2n+1)=3f(n)+1$; so for example $f(22)=f(10110_2)=10110_3=93$.
In fact we notice that $k(n):=h(n)+3f(n)$ has a simple recursion: $$ \begin{align}k(2n)&=h(2n)+3f(2n)=3h(n)+9f(n)=3k(n)\\ k(2n+1)&=h(2n+1)+3f(2n+1)=3h(n)+9f(n)=3k(n)\end{align}$$ Well, this reminds us of the function $l(n)=1+\lfloor \log_2n\rfloor $ that counts the number of binary digits of a number: $l(2n+1)=l(2n)=l(n)+1$. We conclude $k(n)=3^{l(n)-1}k(1)=\frac{11}2\cdot 3^{\lfloor\log_2n\rfloor}$ and ultimately $$ g(n)=\frac{11}2\cdot 3^{\lfloor\log_2n\rfloor}-3f(n)-\frac12.$$ Unfortunately, there is no really "nice" way to express the write-in-binary-read-in-ternary function $f$.