Use induction? for some integer . So, . Obviously, is true, so assume it is true for all nonnegative integers less than or equal to k. Then implies . So, . By the induction assumption, you have , so there exists an integer with . Plug that in and see if you can get .