# Números naturales. Inducción. Recursividad.

## Naturales

En `python` podemos utilizar `isinstance` para determinar si un objeto es un entero


```python
isinstance(4,int)
```




    True




```python
isinstance([3,4],int)
```




    False



Podemos con esta función definir otra que detecte si un objeto es un número es natural


```python
def isnatural(n):
    if not isinstance(n,int):
        return false
    return n>=0
```


```python
isnatural(3)
```




    True




```python
isnatural(-3)
```




    False



La funciones sucesor y predecesor quedarían como sigue


```python
sucesor = lambda x: x+1
```


```python
sucesor(2)
```




    3




```python
def prec(n):
    if not isnatural(n):
        raise TypeError("El argumento debe ser un número natural")
    if n==0: 
        raise ValueError("El 0 no tiene predecesor")
    return n-1
```


```python
prec(1)
```




    0



Con esto podemos definir una suma


```python
def suma(m,n):
    if n == 0:
        return m
    return sucesor(suma(m,prec(n)))
```


```python
suma(2,3)
```




    5



## Sucesiones, inducción

Con la librería `sympy` podemos hacer cálculo simbólico. En particular, podemos calcular el valor de algunas sumas con parámetros. Una ramificación de `sympy`, `diofant`, permite resolver algunos de los problemas que tenía `sympy` con `rsolve`.


```python
from diofant import *
```

Cuando vamos a utilizar un símbolo tenemos que declararlo primero. Para el ejemplo que sigue vamos a utilizar `n` como entero e `i` como contador 


```python
n, i = symbols("n, i", integer = True)
```

### Algunas sumatorias

Calculemos por ejemplo $\sum_{i=1}^n i$


```python
s = Sum(i,(i,1,n))
```


```python
s
```




\begin{equation}\sum_{i=1}^{n} i\end{equation}



Si queremos calcular el "valor" de esta sumatoria, podemos utilizar el método `doit`


```python
s.doit()
```




\begin{equation}\frac{n^{2}}{2} + \frac{n}{2}\end{equation}




```python
pprint(_)
```

     2    
    n    n
    ── + ─
    2    2



```python
summation(i,(i,1,n))
```




\begin{equation}\frac{n^{2}}{2} + \frac{n}{2}\end{equation}



Y una suma de potencias


```python
s=Sum(i**30,(i,1,n))
```


```python
s.doit()
```




\begin{equation}\frac{n^{31}}{31} + \frac{n^{30}}{2} + \frac{5 n^{29}}{2} - \frac{203 n^{27}}{6} + \frac{1131 n^{25}}{2} - \frac{16965 n^{23}}{2} + \frac{216775 n^{21}}{2} - \frac{2304485 n^{19}}{2} + \frac{19959975 n^{17}}{2} - \frac{137514723 n^{15}}{2} + \frac{731482225 n^{13}}{2} - \frac{31795091601 n^{11}}{22} + \frac{8053785025 n^{9}}{2} - \frac{102818379585 n^{7}}{14} + \frac{15626519181 n^{5}}{2} - \frac{23749461029 n^{3}}{6} + \frac{8615841276005 n}{14322}\end{equation}




```python
a = Symbol("a")
```


```python
Sum(a**i,(i,1,n)).doit()
```




\begin{equation}\begin{cases} n & \text{for}\: a = 1 \\\frac{a - a^{n + 1}}{- a + 1} & \text{otherwise} \end{cases}\end{equation}



### Inducción

Veamos cómo podemos utilizar `sympy` para hacer algunos ejemplos de inducción

Por ejemplo, veamos que para todo $6\mid 7^n-1$ para todo $n\in \mathbb N$. Empezamos definiendo una función que nos devuelva $7^n-1$


```python
f = lambda n: 7**n -1
```

Primero veamos qué valor tiene en el 0


```python
f(0)
```




\begin{equation}0\end{equation}



Si por hipótesis de inducción $f(n)$ es un múltiplo de 6, entonces para probar que $f(n+1)$ también lo es, bastará demostrar que la diferencia $f(n+1)-f(n)$ es un múltiplo de 6


```python
simplify(f(n+1)-f(n))
```




\begin{equation}6 \cdot 7^{n}\end{equation}




```python
f = lambda n: 7**(2*n)+16*n-1
```


```python
f(0)
```




\begin{equation}0\end{equation}




```python
simplify((f(n+1)-f(n)) % 64)
```




\begin{equation}16 \operatorname{Mod}{\left (3 \cdot 7^{2 n} + 1,4 \right )}\end{equation}



Por tanto, si $3\times 7^{2n}+1$ es un múltiplo de $4$, habremos acabado


```python
g = lambda n: 3*7**(2*n)+1
```


```python
g(0)
```




\begin{equation}4\end{equation}




```python
simplify((g(n+1)-g(n))%4)
```




\begin{equation}0\end{equation}



### Recursividad e iteración

Veamos cómo las funciones recursivas se pueden acelerar usando memorización de los pasos anteriores


```python
fib = lambda n: n if n<2 else fib(n-2)+fib(n-1)
```


```python
fib(10)
```




\begin{equation}55\end{equation}




```python
fibonacci(10)
```




\begin{equation}55\end{equation}




```python
import time

```


```python
start=time.time()
fib(30)
time.time()-start

```




\begin{equation}0.41254711151123047\end{equation}




```python
start=time.time()
fibonacci(30)
time.time()-start
```




\begin{equation}0.0004341602325439453\end{equation}



Un posible solución a este problema es ir almacenando los resultados previos de cálculo, lo cual es conocido como [memoization](http://stackoverflow.com/questions/1988804/what-is-memoization-and-how-can-i-use-it-in-python)


```python
import functools
```


```python
@functools.lru_cache(maxsize=None)
def fibo(num):
    if num < 2:
        return num
    else:
        return fibo(num-1) + fibo(num-2)
```


```python
start=time.time()
fibo(30)
time.time()-start
```




\begin{equation}0.0001010894775390625\end{equation}



## Resolución de ecuaciones recursivas

Las ecuaciones en recurrencia se pueden resolver con el comando `rsolve` de `sympy`

Empecemos con un ejemplo:
- $a(0)=0$,
- $a(1)=1$,
- $a(n+2)=5a(n+1)-6a(n)$.

Empezamos declarando `a` como función


```python
a = Function('a')
```


```python
rsolve(a(n+2)-5*a(n+1)+6*a(n),a(n))
```




\begin{equation}2^{n} C_{0} + 3^{n} C_{1}\end{equation}




```python
rsolve(a(n+2)-5*a(n+1)+6*a(n),a(n), {a(0):0,a(1):1})
```




\begin{equation}- 2^{n} + 3^{n}\end{equation}



Vamos a resolverlo mediante el polinomio característico


```python
x=Symbol("x")
solve(x**2-5*x+6)
```




\begin{equation}\left [ 2, \quad 3\right ]\end{equation}



Y por tanto la solución general será de la forma $a_n=u 2^n + v 3^n$, para ciertas constantes $u$ y $v$ que tenemos que encontrar a partir de las condiciones iniciales

Imponemos por tanto que $a_0=0=u+v$ y que $a_1=1=2u+3v$


```python
u,v = symbols("u,v")
solve([u+v,2*u+3*v-1])
```




\begin{equation}\left \{ u : -1, \quad v : 1\right \}\end{equation}



Por lo que $a_n=-2^n+3^n$, como habíamos visto arriba

Veamos un ejemplo de una que no sea homogénea


```python
rsolve(a(n+2)-5*a(n+1)+6*a(n)-n,a(n))
```




\begin{equation}2^{n} C_{0} + 3^{n} C_{1} + \frac{n}{2} + \frac{3}{4}\end{equation}



Y ahora otro ejemplo no lineal


```python
f=a(n)-(n-1)*(a(n-1)+a(n-2))
```


```python
rsolve(f,a(n),{a(0):1})
```




\begin{equation}n!\end{equation}




```python
simplify(factorial(n)-(n-1)*(factorial(n-1)+factorial(n-2)))
```




\begin{equation}0\end{equation}



Por último, veamos algunos ejemplos de la relación de problemas


```python
from diofant import *
n=Symbol("n", integer = True)
a=Function('a')
rsolve(a(n)-2*a(n-1)-n,a(n),[1])
```




\begin{equation}3 \cdot 2^{n} - n - 2\end{equation}



Comprobamos la solución


```python
f = lambda n : 3*2**n-n-2
```


```python
f(0)
```




\begin{equation}1\end{equation}




```python
simplify(f(n)-2*f(n-1)-n)
```




\begin{equation}0\end{equation}



Veamos ahora un ejemplo con término no lineal


```python
from diofant import *
n=Symbol("n", integer = True)
x=Function('x')
rsolve(x(n)-2*x(n-1)-3**n,x(n),[1])
```




\begin{equation}- 2 \cdot 2^{n} + 3^{n + 1}\end{equation}




```python
f = lambdify(n,_)
```


```python
f(1)
```




\begin{equation}5\end{equation}




```python
f(n)-2*f(n-1)
```




\begin{equation}- 2 \cdot 2^{n} + 4 \cdot 2^{n - 1} - 2 \cdot 3^{n} + 3^{n + 1}\end{equation}




```python
expand(_)
```




\begin{equation}3^{n}\end{equation}



Otro ejemplo más


```python
rsolve(x(n)-2*x(n-1)-n-2**n,x(n),[0])
```




\begin{equation}2^{n} n + 2 \cdot 2^{n} - n - 2\end{equation}




```python
f = lambda n: n*2**n
```


```python
f(n)-2*f(n-1)
```




\begin{equation}2^{n} n - 2 \cdot 2^{n - 1} \left(n - 1\right)\end{equation}




```python
expand(_)
```




\begin{equation}2^{n}\end{equation}



Los ejemplos anteriores y el siguiente dieron lugar a este [informe de error](https://github.com/diofant/diofant/issues/451)


```python
rsolve(x(n)-2*x(n-1)-3**n*(n+1),x(n),[0])
```




\begin{equation}3 \cdot 2^{n} + 3^{n + 1} \left(n - 1\right)\end{equation}




```python
f = lambda n:3*2**n-3*3**n+3*n*3**n
```


```python
f(0)
```




\begin{equation}0\end{equation}




```python
f(1)
```




\begin{equation}6\end{equation}




```python
f(2)
```




\begin{equation}39\end{equation}




```python
f(n)-2*f(n-1)-(n+1)*3**n
```




\begin{equation}3 \cdot 2^{n} - 6 \cdot 2^{n - 1} + 3 \cdot 3^{n} n - 3^{n} \left(n + 1\right) - 3 \cdot 3^{n} - 2 \cdot 3^{n - 1} \left(3 n - 3\right) + 6 \cdot 3^{n - 1}\end{equation}




```python
expand(_)
```




\begin{equation}0\end{equation}



Resolvamos ahora $x_0=0$, $x_1=1$, $x_n=3x_{n-1}-2x_{n-2}+2^n+2n$. 


```python
rsolve(x(n)-3*x(n-1)+2*x(n-2)-2**n-2*n,x(n),[0,1])
```




\begin{equation}3 \cdot 2^{n} + n \left(2^{n + 1} - n - 5\right) - 3\end{equation}



Hagámoslo ahora a mano. La solución tendrá un polinomio característico asociado $(x-2)(x-1)(x-1)^2(x-2)=(x-2)^2(x-1)^3$. Por tanto la solución será de la forma $x_n=r2^n+sn2^n+t 1^n+u n 1^n + vn^2 1^n$.


```python
def f(n):
    if n==0:
        return 0
    if n==1:
        return 1
    return 3*f(n-1)-2*f(n-2)+2**n+2*n
```


```python
[f(i) for i in range(5)]
```




\begin{equation}\left [ 0, \quad 1, \quad 11, \quad 45, \quad 137\right ]\end{equation}




```python
from diofant import *
```


```python
r,s,t,u,v = symbols("r,s,t,u,v")
n=Symbol("n", integer=True)
eq = lambda n:r*2**n+s*n*2**n+t+u*n+v*n**2
solve([eq(0)-f(0),eq(1)-f(1),eq(2)-f(2),eq(3)-f(3), eq(4)-f(4)],[r,s,t,u,v])
```




\begin{equation}\left \{ r : 3, \quad s : 2, \quad t : -3, \quad u : -5, \quad v : -1\right \}\end{equation}




```python
eq(n).subs(_)
```




\begin{equation}2 \cdot 2^{n} n + 3 \cdot 2^{n} - n^{2} - 5 n - 3\end{equation}




```python
f = lambdify(n,_)
```


```python
simplify(f(n)-3*f(n-1)+2*f(n-2)-2**n-2*n)
```




\begin{equation}0\end{equation}



4bfb59bce5c6e7e4d998ef53906ff9ee4f5e8437
ipynb
Jupyter Notebook
Naturales/Naturales.ipynb
lmd-ugr/LMD
677033858074fc31e0a65885ea424f8ae05591b8
MIT
2016-02-24T09:29:47.000Z
2021-03-23T15:29:52.000Z
Naturales/Naturales.ipynb
pedritomelenas/LMD
cf49271dcb05b1c39339a10a933d30c67b9445f3
MIT
Naturales/Naturales.ipynb
pedritomelenas/LMD
cf49271dcb05b1c39339a10a933d30c67b9445f3
MIT
2016-05-09T14:46:11.000Z
2016-05-09T14:46:11.000Z
Qwen/Qwen-72B
1. YES
2. YES