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.