数学的帰納法

数学的帰納法
自然数nを含んだ命題P(n)が、すべての自然数nについて成り立つことを証明する方法。
(i) n=1のとき、P(1)が成り立つことを示す。
(ii) n=kのとき、P(k)が成り立つと仮定すると、n=k+1のとき、P(k+1)が成り立つことを示す。



(問題)
nを自然数とするとき、6^(n+1) + 7^(2n-1)は43の倍数であることを数学的帰納法によって示せ。

(ヒント)
6^(n+1) + 7^(2n-1)は43の倍数である ⇔ 6^(n+1) + 7^(2n-1)=43×(整数)
となればよい。

(解)
(i) n=1のとき、
6^(n+1) + 7^(2n-1)
=6^(1+1) + 7^(2×1-1) ←n=1を代入
=6^2 + 7^1
=36 + 7
=43
=43×1 ←43×(整数)
よって、n=1のとき、6^(n+1) + 7^(2n-1)は43の倍数である。

(ii) n=kのとき、6^(n+1) + 7^(2n-1)が43の倍数であると仮定すると、
6^(k+1) + 7^(2k-1)=43m (mは整数)
とおける。
これより、
6^(k+1)=43m - 7^(2k-1)……(*) ←(両辺) - 7^(2k-1)

n=k+1のとき、(*)を用いると、
6^(n+1) + 7^(2n-1)
=6^{(k+1)+1} + 7^{2(k+1)-1} ←n=k+1を代入
=6^(k+1)×6 + 7^(2k-1)×7^2
={43m - 7^(2k-1)}×6 + 7^(2k-1)×7^2 ←(*)を代入
=43m×6 - 7^(2k-1)×6 + 7^(2k-1)×7^2
=43×6m + 7^(2k-1)×(-6 + 7^2)
=43×6m + 7^(2k-1)×(-6 + 49)
=43×6m + 7^(2k-1)×43
=43×{6m + 7^(2k-1)} ←43×(整数)
したがって、n=k+1のとき、6^(n+1) + 7^(2n-1)は43の倍数である。

(i)、(ii)より、すべての自然数nについて、6^(n+1) + 7^(2n-1)は43の倍数である。

(コード) (C言語)

#include <stdio.h>
#include <math.h>
int P(int n) {
  unsigned long a = pow(6, n+1) + pow(7, 2*n-1);
  printf("P(%d)=%lu(=43*%lu+%d)\n", n, a, a/43, a%43);
  if (a % 43 == 0) {
    return 1; // true
  } else {
    return 0; // false
  }
}
int main() {
  int i = 1;
  while (i <= 10) {
    if (P(i) != 0) {
      printf("n=%dのとき、P(%d)は成り立つ。\n", i, i);
    } else {
      printf("n=%dのとき、P(%d)は成り立たない。\n", i, i);
      break;
    }
    i = i + 1;
  }
  return 0;
}

(実行結果)

P(1)=43(=43*1+0)
n=1のとき、P(1)は成り立つ。
P(2)=559(=43*13+0)
n=2のとき、P(2)は成り立つ。
P(3)=18103(=43*421+0)
n=3のとき、P(3)は成り立つ。
P(4)=831319(=43*19333+0)
n=4のとき、P(4)は成り立つ。
P(5)=40400263(=43*939541+0)
n=5のとき、P(5)は成り立つ。
P(6)=1977606679(=43*45990853+0)
n=6のとき、P(6)は成り立つ。
P(7)=96890690023(=43*2253271861+0)
n=7のとき、P(7)は成り立つ。
P(8)=4747571587639(=43*110408641573+0)
n=8のとき、P(8)は成り立つ。
P(9)=232630574453383(=43*5410013359381+0)
n=9のとき、P(9)は成り立つ。
P(10)=11398895548170200(=43*265090594143493+1)
n=10のとき、P(10)は成り立たない。

n=10のとき、P(10)=11398895548170199なので、double型からunsigned long型への変換時に誤差が出た模様。