Create an optimal to express all natural number as an arithmetic expression using the alphabet $\Sigma=\{(,),1,+,\times\}$
You can't prove that your algorithm is correct because it isn't. First counter example is n = 46. If we don't bother writing 2 = 1+1 to make it more readable, your algorithm gives
46 = 2 * (1 + 2 * (1 + 2 * (1 + 2 * 2)))

which uses 13 1's.
A better solution is
46 = 1 + ((1 + 2) * ((1 + 2) * (1 + 2 * 2))

which uses only 12 1's.
The difference is bigger for n = 235 (difference 2), n = 649 (difference 3), n = 1,081 (difference = 4), n = 7,849 (difference = 5), n = 33,793 (difference = 6), n = 221,617 (difference = 8).