I will actually execute the program in most cases. Most of the development I do is in the context of a web request (server) or browser DOM (client) so running some quick snippet of code might be as simple as initiating a request from my browser to see what the server does or interacting with it in some other way which triggers the client-side stuff.
You're going to have "something you start with" (input) and "what you want it to be" (output). Understanding these things will go a long way to reason out what you need to actually do to accomplish your goal. Usually a program's "goal" is to "output the correct thing" and the programmer will have to know what "correct" is.
Certainly no formal proofs and I usually work things out "in my head", as it were, because it helps me to understand the problem that I'm working on. See also "rubber ducking" (https://en.wikipedia.org/wiki/Rubber_duck_debugging). It might help to try to build a small program to better wrap your head around "what" programming is.
I just think of the thing I want to build, and I break it into smaller and smaller bits.
I don't write code on paper.. just the "what do I want to happen".. super high level.
Design on paper first, and then convert those paper thoughts into tests. As you're writing your tests out, you'll think of edge cases and it will take a second or two to write a test header for it.
Before you have a line of code, paper and pencil are your best friends.