An example of this would be a permutation of size 32. Can this be of order 62? I assume not because the only way to achieve this would be to have the permutation be made up out of a part with order 2 and one with order 31, but this is impossible.
Am I correct, and what is a formal way of proving this?
On
Each permutation of size $n\geq 1$ can be written as the product of $k\geq 1$ disjoint cycles $C_1,C_2,\dots,C_k$ and the order of $P$ is the least common multiple of the lengths of the cycles.
Hence, there is a permutation of size $n$ of order $m$ if and only $$ \begin{cases} l_1+l_2+\dots+l_k=n\\ \text{lcm}(l_1,l_2,\dots,l_k)=m \end{cases} $$ has a solution with $1\leq l_1\leq l_2\leq \dots\leq l_k$ positive integers and $k\geq 1$.
In your case $n=32$ and $m=62$. Since $62=2\cdot 31$ and $1\leq l_i\leq 32$, it follows easily that there are no solutions. So, yes, you are correct.
You are correct. All permutations consist of cycles, and the order of a permutation is the LCM of its cycle lengths.
Therefore, a permutation of size $n$ can be of order $m$ iff there exist numbers $p_1,p_2,\dots,p_k$ which sum to at most $n$ and multiply to $m$. Clearly, this remains true if the $p_i$ are required to be distinct coprime numbers greater than $1$, which can be used to simplify proofs of (non-)existence.