如何用归纳法证明φ(p^k)=(p^(k-1))(p-1)

Question

如何用归纳法证明φ(p^k) = (p^(k-1))(p-1)

Answer 1

大概步骤如下：
1：假设当n=1时命题成立；
2：证明如果在n=m时成立,那么可以推导n=m+1时命题也成立.
3：从而可以证明此命题成立.
这就是我们常见的数学归纳法.名叫第一归纳法.事实上,数学归纳法可不止这一种形式,他有多种变体,除了我们可以从n=3等开始,或者是只考虑n为奇数偶数等,还有下面的完整归纳法：
1：证明当n=1,2,……,k时命题p(n)成立
2：证明p(m),p(m+1),p(m+2)……,p(m+k-1)成立,能推导出p(m+k)成立.从而证明此命题成立.也就是将第一归纳法里的一个推一个换成多个推一个.我们以一个例子,那就是证明菲波拉契数列的通项公式：
证明：当n=1,2时,可以检验其成立.
假设当n=k和n=k+1时命题皆成立,即：
从而证明了这个通项公式的正确.