Pelo princípio da indução, devemos provar que:

Pelo princípio da indução, devemos provar que uma determinada afirmação é verdadeira para todos os valores de uma variável, geralmente representada por n. O princípio da indução é composto por duas etapas: a base da indução e o passo da indução. Na base da indução, provamos que a afirmação é verdadeira para o valor inicial da variável, geralmente n = 1. Em seguida, no passo da indução, assumimos que a afirmação é verdadeira para um valor k qualquer e provamos que ela também é verdadeira para o valor k + 1. Dessa forma, ao aplicar o princípio da indução corretamente, podemos concluir que a afirmação é verdadeira para todos os valores da variável.