Does iOS 9 update require iOS 8.4.1 to be installed first?
this problem occurs when you already have a downloaded update (for example, you have downloaded 8.4.1 but not installed it yet).
Easiest way to correct is to delete the update (Settings-General-Usage-Manage Storage - look for iOS8.4.1 (or whatever version has been downloaded).

After deleting the old update, a check for software update will show iOS9