嘿，这个问题挺有意思的！咱们用数学归纳法一步步构造出满足条件的多项式，轻松搞定这个证明：

基例：n=1 #

直接取多项式 p(x) = 2（其实任何2的幂都可以，比如2^7），它是整数系数，且p(1)=2是2的幂，完美符合要求。

归纳假设 #

假设当n=k时，已经存在一个整数系数多项式p_k(x)，使得p_k(1), p_k(2), ..., p_k(k)是互不相同的2的幂。

归纳步骤：从n=k到n=k+1 #

我们需要构造一个新的整数系数多项式p_{k+1}(x)，让它既保留前k个点的不同2的幂值，又能让第k+1个点的值是一个全新的2的幂。

构造方法很简单：
$$p_{k+1}(x) = p_k(x) + C \cdot (x-1)(x-2)\cdots(x-k)$$
这里的C是我们要选的整数。

先验证这个多项式的性质：

• 整数系数：p_k(x)本身是整数系数，(x-1)(x-2)...(x-k)展开后也是整数系数，乘以整数C再加到p_k(x)上，结果必然是整数系数多项式。
• 前k个点的取值不变：对任意i=1到k，(i-1)(i-2)...(i-k)=0，所以p_{k+1}(i)=p_k(i)，完全继承了之前互不相同的2的幂。

接下来解决关键问题：找到合适的C，让p_{k+1}(k+1)是一个和前面都不同的2的幂。代入x=k+1可得：
$$p_{k+1}(k+1) = p_k(k+1) + C \cdot k!$$

为什么这样的C一定存在？
2的幂有无穷多个（比如2^1,2^2,2^3,...一直延伸下去），而k!是固定正整数，p_k(k+1)是固定整数。我们可以选一个足够大的2的幂2^m，让它不等于p_k(1)到p_k(k)中的任何一个，然后解出：
$$C = \frac{2^m - p_k(k+1)}{k!}$$
根据数论里的结论，总能找到这样的m，使得2^m - p_k(k+1)是k!的倍数（毕竟2的幂有无穷多，模k!的剩余类有限，鸽巢原理保证必有一个2^m满足同余条件），这样C就是整数。

把这个C代入构造的多项式，p_{k+1}(x)就完全满足要求了：整数系数，且p_{k+1}(1)到p_{k+1}(k+1)是互不相同的2的幂。

结论 #

根据数学归纳法，对所有自然数n，这样的整数系数多项式p(x)都存在。

内容的提问来源于stack exchange，提问作者Ajith Nair