# Can we give an algorithm to prove a statement?

Can we prove a statement by providing an algorithm that is true for all conditions of the statement? Or do we need to prove the validity of the algorithm too?

As an example, suppose we need to prove that each number $n$ can be written as $2^km$ for integers $k, m$, such that $k$ is as large as possible.

We can state an algorithm that will take an integer $n$ and return $k, m$. Let $S = 0$

1. If $n$ is even, add $1$ to $S$ and set $n$ equal to $\frac{n}{2}$. Else, $m = n$ and $k = S$ and exit.

2. Repeat from step 1.

This algorithm will always give us valid values for any integer $n$. It can be seen that the algorithm will exit since $n$ is monotonically decreasing and can only take finite integral values.

For the proof of the statement, is it required to prove the validity of the algorithm?

• That depends on some things, but mainly on what whoever is reading the proof expects. – Git Gud Aug 15 '13 at 14:31

Assume there are counter-examples. Since they are natural numbers, there is a smallest one, call it $S$. $S$ can't be odd, or it is $2^0\cdot S$. So $S$ is even. Consider $S/2$. Since it's smaller, it can't be a counter-example. $S/2 = 2^k m$ for some $k$,$m$. Thus, $S = 2^{k+1} m$, and it isn't a counter-example. Contradiction. Our only assumption was that there were counter-examples. Thus, there are no counter-examples.
You need to prove that the algorithm terminates (it does not terminate if we feed it $n=0$, and indeed for $n=0$ the original claim is also false). And you need to prove that the output your algorithm produces is an answer to the problem (that is, why is $2^km$ the original $n$? And why is $k$ as large as possible?)