Concreto De Las Matemáticas, El Problema 1.16
\[ g(1)=\alpha \]
\[ g(2n+j)=3 g(n)+\gamma n+\beta_j \]
\[ \mbox{para}\ j=0,1\ \mbox{y}\ n\geq1 \]
Solución
Primero vamos a tomar nota de todas las formas de describir $n$
\[ n=2^m+l=(1b_{m-1}b_{m-2}...b_1b_0)_2 \]
También podemos definir la $g(n)$ como una combinación lineal de funciones desconocidas de $n$ y sus correspondientes coeficientes de
\[ g(n)=a(n)\alpha + b(n)\beta_0 + c(n)\beta_1 + d(n)\gamma \]
El siguiente paso es calcular manualmente $g(n)$, para los primeros valores de $n$, en un intento de encontrar un patrón. Después de la observación de la salida de $g(n)$, podemos ver fácilmente que el $a(n)$ es una potencia de $3$. Esta observación sugiere el análisis de la salida de $g(n)$ base $3$
\[
\begin{array}{c|c|c|c|c|c|c}
n & n_2 & a(n)_3 & b(n)_3 & c(n)_3 & d(n)_3 \\
\hline
1 & 1 & 1 & 0 & 0 & 0 \\
\hline
2 & 1\color{red}{0} & 10 & \color{red}{1} & 0 & 1 \\
3 & 1\color{green}{1} & 10 & 0 & \color{green}{1} & 1 \\
\hline
4 & 1\color{red}{00} & 100 & \color{red}{11} & 0 & 12 \\
5 & 1\color{red}{0}\color{green}{1} & 100 & \color{red}{10} & \color{green}{1} & 12 \\
6 & 1\color{green}{1}\color{red}{0} & 100 & \color{red}{1} & \color{green}{10} & 20 \\
7 & 1\color{green}{11} & 100 & 0 & \color{green}{11} & 20 \\
\hline
8 & 1\color{red}{000} & 1000 & \color{red}{111} & 0 & 201 \\
\end{array}
\]
Podemos encontrar rápidamente las $a(n)$, con el repertorio método y una conjetura de $3^m$. Tenga en cuenta que esta conjetura es inspirada en la observación de la salida de $g(n)$
\[ \mbox{Vamos a}\ g(n)=g(2^m+l)=3^m \]
\[ \mbox{Entonces}\ g(1)=g(2^0+0)=3^0=1=\alpha \]
\[ g(2n+j)=g(2^{m+1}+2l+j)=3(3^m)+\gamma n+\beta_j\]
\[ 3^{m+1}= 3^{m+1}+\gamma n +\beta_j\]
Lo que implica que
\[ 0= \gamma n+\beta_j \]
\[ \alpha=1, \beta_0=0, \beta_1=0, \gamma=0 \]
\[ 3^m =1a(n) + 0(n) + 0(n) + 0d(n) \]
Así
\[ a(n) = a(2^m + l) = 3^m \]
Con el fin de encontrar $b(n)$, debemos observar que para todos los bits binarios $b_x$ $n$ donde$x < m$$b_x=0$, hay un complejo de dos dígitos $1$ en la salida de $b(n)$ en la posición $x$. Esta relación se expresa en la tabla de arriba en rojo y con un poco de un generador de notación a continuación. Tenga en cuenta que $0\in\mathbb{N}$, como es muy natural, no tener nada
\[ b(n)=\sum \{3^x : (\exists x)(x\in\mathbb{N}, x < m, b_x=0)\} \]
Curiosamente, la búsqueda de $c(n)$ es similar con la excepción de que $b_x=1$. Esto se expresa también en la tabla de arriba en verde y a continuación de la siguiente manera
\[ c(n)=\sum \{3^x : (\exists x)(x\in\mathbb{N}, x < m, b_x=1)\} \]
Después de definir $a(n)$, $b(n)$ y $c(n)$, la siguiente ecuación se convierte en casi trivial
\[ a(n)\alpha + b(n)\beta_0 + c(n)\beta_1 = (\alpha\beta_{b_{m-1}}\beta_{b_{m-2}}...\beta_{b_1}\beta_{b_0})_3 \]
Ahora podemos encontrar $d(n)$, con el repertorio método y un estándar de estimación de $n$
\[ \mbox{Vamos a}\ g(n)=n \]
\[ \mbox{Entonces}\ g(1)=1=\alpha \]
\[ g(2n+j)=3n+\gamma n+\beta_j\]
\[ 2n+j= 3n+\gamma n +\beta_j\]
Lo que implica que
\[ -n+j= \gamma n+\beta_j \]
\[ \alpha=1, \beta_0=0, \beta_1=1, \gamma=-1 \]
\[ n =1a(n) + 0(n) + 1c(n) - 1d(n) \]
Así
\[ d(n) = a(n)+c(n)-n \]
Así que ahora tenemos las soluciones
\[ a(n) = 3^m \]
\[ b(n)=\sum \{3^x : (\exists x)(x\in\mathbb{N}, x < m, b_x=0)\} \]
\[ c(n)=\sum \{3^x : (\exists x)(x\in\mathbb{N}, x < m, b_x=1)\} \]
\[ d(n) = a(n)+c(n)-n \]
He aquí un breve ejemplo de cómo calcular $a(n)$, $b(n)$, $c(n)$ y $d(n)$
\[ \mbox{Vamos a}\ n=19=2^4+3=(10011)_2\]
\[ un(19)=3^4=81=(10000)_3 \]
\[ b(19)=3^2+3^3=36=(1100)_3 \]
\[ c(19)=3^0+3^1=4=(11)_3 \]
\[ d(19)=81+4-19=66=(2110)_3 \]
Esto es bueno, pero, que podemos hacer mejor. Permite simplificar esta solución por encontrar otra ecuación mediante el método repertorio
\[ \mbox{Vamos a}\ g(n)=1 \]
\[ \mbox{Entonces}\ g(1)=1=\alpha \]
\[ g(2n+j)=3(1)+\gamma n+\beta_j\]
\[ 1= 3+\gamma n +\beta_j\]
Lo que implica que
\[ -2= \gamma n+\beta_j \]
\[ \alpha=1, \beta_0=-2, \beta_1=-2, \gamma=0 \]
\[ 1 =1a(n) -2b(n) -2c(n) +0d(n) \]
Así
\[ b(n) = \frac{1}{2}(a(n)-1)-c(n) \]
Ahora podemos expresar $b(n)$ en términos de$a(n)$$c(n)$, eliminando así la suma. Así que vamos a poner todo junto
\[ g(n)=a(n)\alpha + (\frac{1}{2} (n)-\frac{1}{2}-c(n))\beta_0 + c(n)\beta_1 + (a(n)+c(n)-n)\gamma \]
\[ g(n)=a(n)\alpha + \frac{1}{2} (n)\beta_0-\frac{1}{2}\beta_0-c(n)\beta_0 + c(n)\beta_1 + a(n)\gamma+c(n)\gamma-n\gamma \]
\[ g(n)=a(n)(\alpha + \frac{1}{2}\beta_0+\gamma)+ c(n)(\beta_1 -\beta_0+\gamma)-n\gamma\frac{1}{2}\beta_0 \]
Por lo tanto, la forma cerrada de la solución es
\[ \mbox{Vamos a}\ S= \{3^x : (\exists x)(x\in\mathbb{N}, x < m, b_x=1)\} \]
\[ g(n)=3^m(\alpha + \frac{1}{2}\beta_0+\gamma)+ (\beta_1 -\beta_0+\gamma) \la suma de S - n\gamma\frac{1}{2}\beta_0 \]
Espero que esto les ayude a entender.
