Ask HN: Can you “sell” more Bitcoin than you actually own?

Say I run a wallet service where users can buy bitcoins from me and keep them in their "online wallet". When a user clicks "buy", do I have to actually buy bitcoins for the user?

Or can I just simply update my database to increment their balance when a user clicks "buy"?

What happens if I try to "sell" more Bitcoins than I own? For a service like Coinbase, is there a way for them to prove that they actually have the bitcoins for a user?