Digamos que você esteja em uma festa com outras nove pessoas e todos apertem a mão de todos exatamente uma vez. Quantos apertos de mão acontecem?

Este é o “problema do aperto de mão” e é um dos meus favoritos. Como professor de matemática, adoro isso porque existem muitas maneiras diferentes de chegar à solução, e a diversidade e a interconexão dessas estratégias ilustram lindamente o poder do pensamento criativo em matemática.

Uma solução é a seguinte: comece com cada pessoa apertando a mão uma da outra. Dez pessoas, com nove apertos de mão cada, produzem 9 × 10 = 90 apertos de mão no total. Mas isso conta cada aperto de mão duas vezes — uma vez da perspectiva de cada shaker — então o número real de apertos de mão é $latex frac{90}{2} = 45$. Um argumento de contagem simples e adorável para a vitória!

Também existe uma maneira completamente diferente de resolver o problema. Imagine que os convidados chegam um de cada vez e, ao chegarem, apertam a mão de todos os presentes. A primeira pessoa não tem mãos para apertar, portanto, em uma festa individual, o total de apertos de mão é zero. Agora a segunda pessoa chega e aperta a mão da primeira pessoa. Isso adiciona um aperto de mão ao total, portanto, em um grupo de duas pessoas, há 0 + 1 = 1 apertos de mão no total. Quando a terceira pessoa chega e aperta a mão dos dois primeiros convidados, isso soma dois apertos de mão ao total. A chegada da quarta pessoa soma três apertos de mão ao total e assim por diante.

Essa estratégia modela a sequência de handshakes recursivamente, o que significa que cada termo da sequência é definido em relação aos que vêm antes dele. Você provavelmente conhece a sequência de Fibonacci, a sequência recursiva mais famosa de todas. Começa com 1, 1, 2, 3, 5, 8, 13, 21 e continua com cada termo subsequente igual à soma dos dois anteriores.

Como veremos a seguir, a recursão é uma estrutura flexível e poderosa para pensar sobre uma ampla gama de ideias matemáticas. E embora antigos estudiosos indianos como Hemachandra sejam creditados por conhecerem esses tipos de sequências já em 1150, eles ainda oferecem desafios intrigantes para os matemáticos de hoje.

Vamos ver como o pensamento recursivo ajuda no problema do aperto de mão. Se deixarmos $latex a_n$ igual ao número de apertos de mão em um n-person party, podemos representar essa relação recursiva com a seguinte fórmula:

$látex a_n = a_{n-1} + n–1$

Isso nos diz que o número de apertos de mão em um n-person party ($latex a_n$) é igual ao número de apertos de mão em um (n − festa de 1) pessoa ($latex a_{n-1}$) mais n − Mais 1 aperto de mão, captando a ideia de que quando chega uma nova pessoa acrescenta um certo número de novos apertos de mão aos que já ocorreram.

Em nossa versão específica do problema do aperto de mão, queremos saber $latex a_{10}$, o número de apertos de mão em uma festa de 10 pessoas, então, para descobrir que usamos o relacionamento recursivo

$látex a_{10} = a_9 + 9$

Para encontrar o valor de $latex a_{10}$, só precisamos saber o valor de $latex a_9$ e adicionar 9 a ele. Como encontramos o valor de $látex a_9$? Usando recursão, é claro!

$látex a_9 = a_8 + 8$

Agora, para encontrar o valor de $latex a_8$, precisamos encontrar o valor de $latex a_7$, o que requer conhecer $latex a_6$, e assim por diante. Neste ponto, você pode estar preocupado que isso continue para sempre em uma espécie de descida infinita, mas quando chegarmos a $latex a_1$ estaremos prontos, porque sabemos que há zero apertos de mão em uma festa individual.

$látex a_1 = 0$

Este valor inicial ou “semente” é um recurso chave de uma sequência recursiva. Garante que esse processo de retrocesso na sequência usando o relacionamento recursivo terminará. Depois de atingir o valor inicial, o retrocesso para e você pode avançar na lista para obter o valor desejado.

$látex a_1 = 0$

$látex a_2 = a_1 + 1 = 0 + 1 = 1$

$látex a_3 = a_2 + 2 = 1 + 2 = 3$

$látex a_4 = a_3 + 3 = 3 + 3 = 6$

$cdots de látex$

$látex a_{10} = a_9 + 9 = 36 + 9 = 45$

Ao analisar a lista, vemos que há um total de 45 apertos de mão numa festa de 10 pessoas, o que está de acordo com o nosso cálculo inicial. Se você for como meus alunos, poderá perguntar por que precisamos de outra maneira de resolver esse problema quando já sabemos a resposta, especialmente porque essa segunda abordagem parece demorar mais.

É uma boa pergunta. Uma resposta é que a abordagem recursiva nos dá uma visão totalmente diferente do que está acontecendo neste problema, e diferentes perspectivas são úteis em matemática, como o são em todas as coisas. Eles nos dão diferentes oportunidades para compreender conceitos e nos permitem utilizar diferentes ferramentas, que podem ajudar quando estamos travados.

Em particular, a recursão é útil porque está em toda parte na matemática. Surge, por exemplo, nas relações lineares que todos aprendem nas aulas de matemática – aquelas caracterizadas por uma taxa constante de mudança e representadas por linhas no plano. Uma função linear como $latex f(x) = 3x + 5$ pode ser considerada uma fórmula recursiva:

$látex a_0 = 5$

$látex a_n = a_{n-1} + 3$

Embora a maneira mais óbvia de pensar sobre $latex f(2)$ possa ser que $latex f(2) = 3 vezes 2 + 5 = 11$, outra maneira é que $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. A modelagem recursiva da característica fundamental das funções lineares — a taxa constante de variação — nos dá outra maneira de pensar sobre essa relação. O mesmo pode ser feito com funções exponenciais caracterizadas por variação multiplicativa constante.

O pensamento recursivo também funciona além das sequências de números. Se você já resolveu um sistema de equações, provavelmente aplicou uma abordagem recursiva. Para resolver o sistema

$látex 2x + y = 10$

$látex 3x – y = 5$

você pode primeiro adicionar as duas equações para eliminar o y variável, que resulta na equação $latex 5x = 15$. Resolva isso para obter $latex x =$ 3, substitua para encontrar $latex y = 4$ e pronto. Esta abordagem utiliza um algoritmo recursivo, onde a solução para um sistema é construída a partir da solução para sistemas menores relacionados. Por exemplo, para resolver um sistema 3 × 3, você elimina uma variável para transformá-la em um sistema 2 × 2 e, novamente, para transformá-la em um sistema 1 × 1. Essa equação única e fácil de resolver é como o valor inicial desse processo recursivo. Ele sinaliza o fim do retrocesso e, a partir daí, você volta para cima na cadeia de equações, como em uma sequência recursiva.

Existem até técnicas de prova recursivas. Por exemplo, uma fórmula famosa em geometria é a fórmula da soma dos ângulos poligonais, que diz que a soma das medidas dos ângulos internos de um nO polígono de dois lados é $latex (n-2) vezes 180^{circ}$. Uma maneira de provar esse resultado é começar com um n-Vá e imagine o que aconteceria se você removesse um triângulo.

A remoção de um triângulo transforma o n-entra em um (n − 1)-gon, e também remove 180 graus da medida do ângulo interno. Esta é uma relação recursiva: a soma dos ângulos internos para um n-gon é 180 graus a mais que a soma do ângulo interno para um (n − 1)-gon. Para estabelecer o resultado geral, continue removendo triângulos até atingir o valor inicial, o que nesta situação acontece quando você removeu todos os triângulos, exceto três. n-gon vértices. Neste ponto, o polígono inicial foi reduzido a um triângulo, cuja soma dos ângulos internos é conhecida como 180 graus. Agora volte para cima, adicionando 180 graus em cada etapa, e você obterá a fórmula.

Voltando à nossa festa, o próprio problema do aperto de mão nos mostra o que é possível quando pensamos criativamente e então conectamos essas múltiplas perspectivas diferentes de um problema. Se brincarmos com o modelo recursivo para nossa sequência de apertos de mão:

$látex a_1 = 0$

$látex a_n = a_{n-1} + n – 1$

surge um belo padrão:

$látex a_2 = a_1 + 1 = 0 + 1$

$látex a_3 = a_2 + 2 = 0 + 1 + 2$

$látex a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$cdots de látex$

$látex a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

Agora temos uma maneira nova e geral de pensar sobre o problema: o número de apertos de mão em um n-pessoa parte é igual à soma da primeira n − 1 inteiros positivos.

Pense novamente em nossa abordagem original. Em um n- festa de pessoa, cada pessoa apertará a mão da outra n − 1 pessoa. O produto $latex n (n-1)$ conta cada aperto de mão duas vezes, então o número total de apertos de mão é $latex frac{n(n-1)}{2}$. Mas como os nossos diferentes métodos contam a mesma coisa, têm de produzir o mesmo resultado. Em particular, isso significa:

$látex 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

Ao conectar diferentes abordagens para o problema do aperto de mão, obtemos uma fórmula fechada para a soma dos primeiros n − 1 inteiros positivos. Mas temos ainda mais: a expressão $latex frac{n(n-1)}{2}$ envolve uma fração, mas por ser igual a uma soma de números inteiros, também deve ser um número inteiro. Isso prova um fato simples da teoria dos números: para cada número inteiro n, $latex frac{n(n-1)}{2}$ é um número inteiro.

Este mesmo tipo de argumento continua a impulsionar a matemática moderna. Por exemplo, pesquisadores no início dos anos 2000 provou alguns resultados surpreendentes sobre sequências recursivas conhecidas como sequências Somos, mostrando que elas também contam alguma coisa. Através do poder das conexões criativas, os matemáticos descobriram mais uma vez onde poderiam chegar ao compreenderem onde estiveram.

Exercícios

1. Encontre uma fórmula fechada para a sequência que é definida recursivamente como
$látex a_1 = 1$
$látex a_n = a_{n-1} + 2n – 1$

2. No final da coluna, a expressão $latex frac{n(n-1)}{2}$ foi mostrada como um número inteiro, embora a expressão envolva uma fração, porque $latex frac{n(n-1 )}{2}$ é o resultado da contagem de algo. Há também um argumento da teoria dos números que mostra que esta expressão deve ser um número inteiro. O que é?

3. Encontre os primeiros termos da sequência recursiva
$látex a_1 = 1$
$látex a_n = frac{1}{1+a_{n-1}}$

4. Encontre os primeiros termos da sequência recursiva
$látex a_1 = 1$
$látex a_2 = 1$
$látex a_n = a_{n-1} – a_{n-2}$