# Somas e Recorrências

A soma

$$S_n = \sum_{k=0}^n a_k$$

é equivalente à recorrência

\begin{align}
S_0 &= a_0;\\
S_n &= S_{n-1} + a_n, \qquad \text{para}\ n>0.
\end{align}

## Manipulação de somas

$$\sum_{k\in K}c\ a_k = c \sum_{k\in K}a_k \qquad \text{(lei distributiva)}$$
$$\sum_{k\in K}(a_k + b_k) =  \sum_{k\in K}a_k + \sum_{k\in K}b_k \qquad \text{(lei associativa)}$$
$$\sum_{k\in K}a_k =  \sum_{p(k)\in K}a_{p(k)} \qquad \text{(lei comutativa)}$$

# Funções de Inteiros

## Piso e teto

**Piso** (*floor*): $\lfloor x\rfloor$ = o maior inteiro menor ou igual a $x$. Exemplos:

$\lfloor 2,3\rfloor = 2$, $\qquad\lfloor 2,7\rfloor = 2$, $\qquad\lfloor -2,7\rfloor = -3$.

**Teto** (*ceil*): $\lceil x\rceil$ = o menor inteiro maior ou igual a $x$.

$\lceil 2,3\rceil = 3$, $\qquad\lceil 2,7\rceil = 3$, $\qquad\lceil -2,7\rceil = -2$.


```python
import math
nums = [2.3, 2.7, -2.7]
print("Números:", nums)
pisos = [math.floor(nums[0]), math.floor(nums[1]), math.floor(nums[2])]
print("Pisos:", pisos)
tetos = [math.ceil(nums[0]), math.ceil(nums[1]), math.ceil(nums[2])]
print("Tetos:", tetos)
```

    Números: [2.3, 2.7, -2.7]
    Pisos: [2, 2, -3]
    Tetos: [3, 3, -2]


# Operação Módulo

A partir da fórmula básica

$$x = y\lfloor x/y\rfloor + x\ \text{mod}\ y $$

onde

$\lfloor x/y\rfloor$ é o quociente da divisão;

$x\ \text{mod}\ y$ é o resto da divisão.

Obtemos

$$x\ \text{mod}\ y = x - y\lfloor x/y \rfloor$$

**Exemplos**

\begin{align}
5\ \text{mod}\ 3 & = \ 5 - 3\lfloor 5/3 \rfloor &=&\quad 5 - (3 \times 1) & = &\quad 2\\
5\ \text{mod}\ -3 & = \ 5 - (-3)\lfloor 5/(-3) \rfloor & = &\quad 5 - (-3 \times -2)  & = & -1\\
-5\ \text{mod}\ 3 & = \ -5 - 3\lfloor -5/3 \rfloor & = &\quad -5 - (3\times -2) & = & \quad 1\\
-5\ \text{mod}\ -3 & = \ -5 - (-3)\lfloor -5/(-3) \rfloor & = &\quad -5 - (-3 \times 1) & = & -2\\
\end{align}


```python
# Em Python e C, o operador módulo (mod) é `%`
x=5; y=3
print(' {} mod  {} =  {}'.format(x, y, x % y))
print(' {} mod {} = {}'.format(x, -y, x % -y))
print('{} mod  {} =  {}'.format(-x, y, -x % y))
print('{} mod {} = {}'.format(-x, -y, -x % -y))
```

     5 mod  3 =  2
     5 mod -3 = -1
    -5 mod  3 =  1
    -5 mod -3 = -2


**Aplicações**

# *Bibliografia*

- Judy Graham, Donald Knuth, Oren Patashnik. 
"[Matemática Concreta: Fundamentos Para a Ciência da Computação](https://www.amazon.com.br/Matem%C3%A1tica-Concreta-Fundamentos-Ci%C3%AAncia-Computa%C3%A7%C3%A3o/dp/8521610408)".
LTC Editora; 2ª edição, 1995.

ae8f35d258c826fafcb06ad0b548c45c9373e383
ipynb
Jupyter Notebook
notebooks/MD-Semana07.ipynb
prof-holanda/matematica-discreta
83e3a1b008baf11a11cddc5148f85c523531bf16
CC0-1.0
notebooks/MD-Semana07.ipynb
prof-holanda/matematica-discreta
83e3a1b008baf11a11cddc5148f85c523531bf16
CC0-1.0
notebooks/MD-Semana07.ipynb
prof-holanda/matematica-discreta
83e3a1b008baf11a11cddc5148f85c523531bf16
CC0-1.0
2021-05-18T13:25:27.000Z
2021-05-18T13:25:27.000Z
Qwen/Qwen-72B
1. YES
2. YES