A=(1110),b0=0, b1=1,bn+2=bn+1+bn(n=0,1,2,…).
E는 2행 2열 단위행렬이다. 모든 자연수 n에 대하여 Aⁿ=bₙA+bₙ₋₁E임을 증명하라.
직접 계산하면 A²=A+E이고 n=1에서 b₁A+b₀E=A다. n=k에서 식이 맞다고 놓고 오른쪽에 A를 곱하면
Ak+1=bkA2+bk−1A=bk(A+E)+bk−1A=bk+1A+bkE.
수학적 귀납법으로 증명이 끝난다. A와 E의 1행 2열 성분은 각각 1과 0이므로 Aⁿ의 그 성분은 bₙ이다.
작은 n에서 수열의 항을 발견한 답과, 임의의 k에서 두 계수가 어떻게 바뀌는지 보인 답을 구별한다. 다음 줄로 넘어갈 때 사용하는 관계는 A²=A+E와 bₖ₊₁=bₖ+bₖ₋₁ 두 개다. b₀=0도 첫 단계에 필요하다.
출처·착안: srcav, 「Grid Method Matrix Multiplication」. 문항과 풀이는 새로 작성했다.
