Doesn't a logical proof count as evidence? To my mind, these two methods are demonstrating the same thing: considering all the possible inputs, we can show [using logic|by testing them all] that the output meets our criteria.
To my mind, in this context, the difference between maths and physics is that maths is exhaustive while in physics we don't usually have exhaustive evidence so we have to work with what we've got.
Interesting question - to me, the distinction is that 'evidence' of the validity of something is expected output(s) given known input(s), whereas 'proof' (at least in the mathematical sense) is a logical transformation that is applied to make it obvious that the theorem must be true. I'm not sure you could call a proof 'evidence' because it's not an output of the theorem - it is the theorem.
I'm less certain than I was before I read your post, though - so I stand to be corrected :-)
To my mind, in this context, the difference between maths and physics is that maths is exhaustive while in physics we don't usually have exhaustive evidence so we have to work with what we've got.