Simple and not-so-tricky (really)

${ 2016 }^{ 1008 }<{ n }^{ 2016 }\\ \sqrt [ 2016 ]{ { 2016 }^{ 1008 } } <\sqrt [ 2016 ]{ { n }^{ 2016 } } \\ \Rightarrow \quad n>\sqrt { 2016 } \\$

The smallest natural number $n$ is therefore 45.