Belief does not necessarily come from provability. Wittgesnstein's On Certainty contains some interesting thoughts in this regard. Quoting a few extracts:

"If you tried to doubt everything you would not get as far as doubting anything. The game of doubting itself presupposes certainty."

"Giving grounds, however, justifying the evidence, comes to an end."

"At the foundation of well-founded belief lies belief that is not founded."

"The child learns to believe a host of things. I.e. it learns to act according to these beliefs. Bit by bit there forms a system of what is believed, and in that system some things stand unshakeably fast and some are more or less liable to shift. What stands fast does so, not because it is intrinsically obvious or convincing; it is rather held fast by what lies around it."