If you use iCloud backup and don't ever sync to a local iTunes, then you're out of luck. If you sync with a local iTunes, the app will be in iTunes and will be installed to the device. Unless of course something on the new device prevents the app from running due to technical reasons, but that's the same with old games and new hardware/OSes