Allan Hirt notes that you need KB2919355 installed before you can install SQL Server 2016 on Windows Server 2012 R2 or Windows 8.1:
In my case, I created a new VM with a fresh installation of Windows Server 2012 R2. I also ran Windows Update to ensure it had everything Windows Server thought it required. Figure 3 reflects this status.
As you can see in Figure 4, KB2919355 is not listed as one of the ones WU installed, so it has to be an optional update.
Looking at the list of optional updates in Windows Update in Figure 5, 2919355 is not shown. This means you need to download and install it manually.
It’s never quite as easy as “just run this patch,” so do read on for another gotcha.