Indução 
Quantas jogadas?
O exemplo usado para descrever uma iniciação ao raciocínio de indução foi propositadamente escolhido por forma a não envolver explicitamente nenhuma afirmação quantitativa. E não há, pois, nenhuma fórmula concreta a ser demonstrada. Tomando como ponto de partida esse exemplo, vamos agora encarar a questão da contagem do número mínimo de jogadas que serão/seriam necessárias para concretizar o jogo das lâmpadas.
Fig 7
Designemos por \(f(n)\) o número mínimo de jogadas para concluir o jogo com uma fila de \(n\) lâmpadas todas inicialmente apagadas. Claro que \(f(1)=1\) e do que vimos atrás resulta que \(f(2)=3\) e \(f(3)=7\). Vimos como, conhecendo um caminho para o jogo com uma fila de \(n\) lâmpadas, também conhecemos para uma fila com mais uma lâmpada: antes de acendermos essa última lâmpada de ordem \(n+1\), temos de ter acesa apenas a anterior de ordem \(n\) (com \(f(n)\) cliques), depois acendemos com um clique a de ordem \(n+1\) e finalmente, outra vez com os mesmos \(f(n)\) cliques (pela mesma ordem), apagamos a de ordem \(n\). Ao todo usámos \(f(n)+1+f(n)\) cliques e não podíamos ter usado menos, portanto concluímos que \(f(n+1)=2f(n)+1\). É fácil calcular a partir desta igualdade os primeiros valores do número de cliques necessários:
Fig 8
Repare o leitor que todos os números obtidos precedem imediatamente potências de \(2\). Será que, para qualquer \(n\), \(f(n)=2^{n}-1\)? A igualdade é válida para \(n=1\): \(f(1)=1=2^{1}-1\); se houvesse algum número para o qual ela não fosse válida, haveria um primeiro número, necessariamente diferente de \(1\) para o qual seria errada. Chamando \(p\) ao seu antecessor, teríamos \(f(p) = 2^{p}-1\) e \(f(p+1)\neq2^{p+1}-1\). Mas já vimos que \(f(p+1) = 2f(p)+1 = 2(2^{p}-1)+1 = 2^{p+1}-1\), contrariamente ao que supuséramos (que era haver um primeiro número \(p+1\) para o qual a igualdade não se verificava). Portanto, está provado que aquela fórmula é válida para qualquer \(n\).
Fazendo as contas para o caso da hipotética afirmação do leitor, referida no final da última secção, chegamos à conclusão que seriam precisos \(2^{37}-1=137 438 953 471\) movimentos para jogar o jogo com uma fila de \(37\) lâmpadas. Um leitor com uma velocidade1 de cliques da ordem de \(7\) por segundo, se pudesse estar permanentemente a jogar, noite e dia, num ano bissexto teria feito \(7.60.60.24.366 = 221 356 800\) cliques. Ora, mesmo nessas condições completamente irrealistas, demoraria cerca de 621 anos2 para completar o jogo…
O leitor poderá retorquir que então o raciocínio de indução falha na hipotética afirmação sobre a sua capacidade de jogar o jogo das 37 lâmpadas. A resposta é: o raciocínio em si não está a falhar, o que acontece é que não se verifica uma das condições da indução para a afirmação de que é capaz de jogar… Não é verdade que, se o jogador é capaz de jogar para \(n\) lâmpadas, então também é para \(n+1\).3
