I don't know why everyone always suggests the USB install disk method to clean install a new OS. It's long, complicated, and requires buying a 16GB USB stick if you don't have one.
There's an easier way, particularly if you only have one computer you want to clean install:
When you boot from the recovery partition it allows you to erase the boot drive and reinstall the last installed version of macOS.
Now, at this stage you probably have El Capitan installed, so you need to download Sierra from the App Store and upgrade as usual. Then once it is installed, restart your computer and hold down command R at restart to boot from recovery partition.
Use disk utility to erase your boot disk then reinstall macOS.
Hope that helps!