Números naturales. Inducción. Recursividad.

Naturales

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



In [1]:

    
isinstance(4,int)









    Out[1]:





True



In [2]:

    
isinstance([3,4],int)









    Out[2]:





False

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



In [3]:

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



In [4]:

    
isnatural(3)









    Out[4]:





True



In [5]:

    
isnatural(-3)









    Out[5]:





False

La funciones sucesor y predecesor quedarían como sigue



In [6]:

    
sucesor = lambda x: x+1



In [7]:

    
sucesor(2)









    Out[7]:





3



In [8]:

    
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



In [9]:

    
prec(1)









    Out[9]:





0

Con esto podemos definir una suma



In [10]:

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



In [11]:

    
suma(2,3)









    Out[11]:





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.



In [12]:

    
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



In [13]:

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

Algunas sumatorias

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



In [14]:

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



In [15]:

    
s









    Out[15]:





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

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



In [16]:

    
s.doit()









    Out[16]:





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



In [17]:

    
pprint(_)



In [18]:

    
summation(i,(i,1,n))









    Out[18]:





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

Y una suma de potencias



In [19]:

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



In [20]:

    
s.doit()









    Out[20]:





\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}



In [21]:

    
a = Symbol("a")



In [22]:

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









    Out[22]:





\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$



In [23]:

    
f = lambda n: 7**n -1

Primero veamos qué valor tiene en el 0



In [24]:

    
f(0)









    Out[24]:





\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



In [25]:

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









    Out[25]:





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



In [26]:

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



In [27]:

    
f(0)









    Out[27]:





\begin{equation}0\end{equation}



In [28]:

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









    Out[28]:





\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



In [29]:

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



In [30]:

    
g(0)









    Out[30]:





\begin{equation}4\end{equation}



In [31]:

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









    Out[31]:





\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



In [32]:

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



In [33]:

    
fib(10)









    Out[33]:





\begin{equation}55\end{equation}



In [34]:

    
fibonacci(10)









    Out[34]:





\begin{equation}55\end{equation}



In [35]:

    
import time



In [36]:

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









    Out[36]:





\begin{equation}0.41254711151123047\end{equation}



In [37]:

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









    Out[37]:





\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



In [38]:

    
import functools



In [39]:

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



In [40]:

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









    Out[40]:





\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



In [41]:

    
a = Function('a')



In [42]:

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









    Out[42]:





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



In [43]:

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









    Out[43]:





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

Vamos a resolverlo mediante el polinomio característico



In [44]:

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









    Out[44]:





\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$



In [45]:

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









    Out[45]:





\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



In [46]:

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









    Out[46]:





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

Y ahora otro ejemplo no lineal



In [47]:

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



In [48]:

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









    Out[48]:





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



In [49]:

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









    Out[49]:





\begin{equation}0\end{equation}

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



In [50]:

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









    Out[50]:





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

Comprobamos la solución



In [51]:

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



In [52]:

    
f(0)









    Out[52]:





\begin{equation}1\end{equation}



In [53]:

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









    Out[53]:





\begin{equation}0\end{equation}

Veamos ahora un ejemplo con término no lineal



In [54]:

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









    Out[54]:





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



In [55]:

    
f = lambdify(n,_)



In [56]:

    
f(1)









    Out[56]:





\begin{equation}5\end{equation}



In [57]:

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









    Out[57]:





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



In [58]:

    
expand(_)









    Out[58]:





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

Otro ejemplo más



In [59]:

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









    Out[59]:





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



In [60]:

    
f = lambda n: n*2**n



In [61]:

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









    Out[61]:





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



In [62]:

    
expand(_)









    Out[62]:





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

Los ejemplos anteriores y el siguiente dieron lugar a este informe de error



In [63]:

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









    Out[63]:





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



In [64]:

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



In [65]:

    
f(0)









    Out[65]:





\begin{equation}0\end{equation}



In [66]:

    
f(1)









    Out[66]:





\begin{equation}6\end{equation}



In [67]:

    
f(2)









    Out[67]:





\begin{equation}39\end{equation}



In [68]:

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









    Out[68]:





\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}



In [69]:

    
expand(_)









    Out[69]:





\begin{equation}0\end{equation}

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



In [70]:

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









    Out[70]:





\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$.



In [71]:

    
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



In [72]:

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









    Out[72]:





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



In [73]:

    
from diofant import *



In [74]:

    
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])









    Out[74]:





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



In [75]:

    
eq(n).subs(_)









    Out[75]:





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



In [76]:

    
f = lambdify(n,_)



In [77]:

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









    Out[77]:





\begin{equation}0\end{equation}