SICP 연습문제 1.13 친절한 풀이

문제

$ϕ=(1+\sqrt{5})/2$일때 $Fib(n)$이 $ϕ^n/5$에 가장 가까운 정수임을 증명하라.

참고)
$ψ=(1-\sqrt{5})/2$일때
$Fib(n)=(ϕ^n-ψ^n)/\sqrt{5}$을 증명하라.

문제로 부터 얻은 것

수학문제를 풀고 마크다운으로 설명하는 짓은 미친 짓이다.

문제풀이

수식이 난해할 수 있으니 천천히 읽어주시기 바랍니다.

a. $Fib(n)=(ϕ^n-ψ^n)/\sqrt{5}$ 증명

$(ϕ^n-ψ^n)/\sqrt{5}$를 변형해 보면 피보나치 수열의 특징을 발견할 수 있다.

$f(n)=(ϕ^n-ψ^n)/\sqrt{5}$이라고 하자.

$f(n+1)$
$=(ϕ^{n+1}-ψ^{n+1})/\sqrt{5}$
$=(ϕ\timesϕ^{n}-ψ\timesψ^{n})/\sqrt{5}$

$f(n)+f(n+1)=((ϕ+1)ϕ^n-(ψ+1)ψ^n)/\sqrt{5}$

그런데 수를 대입해서 계산해 보면,
$ϕ+1=ϕ^2$,$ψ+1=ψ^2$라는 것을 알수 있으므로

$f(n)+f(n+1)$
$=((ϕ+1)ϕ^n-(ψ+1)ψ^n)/\sqrt{5}$
$=((ϕ^2)ϕ^n-(ψ^2)ψ^n)/\sqrt{5}$
$=(ϕ^{n+2}-ψ^{n+2})/\sqrt{5}$
$=f(n+2)$

$∴ f(n)+f(n+1)=f(n+2)$

f(n)은 피보나치 수열의 규칙을 따름을 알 수 있다.

b. $Fib(n)$이 $ϕ^n/\sqrt{5}$에 가장 가까운 정수임을 증명

어떤 수를 $x$라 하고, $x$에 가장 가까운 정수를 $n$이라 한다면,
$n$은 ($x-0.5≤ n ≤ x+0.5$)를 만족하는 수이다.

$Fib(n)$
$=(ϕ^n-ψ^n)/\sqrt{5}$
$=\frac{ϕ^n}{\sqrt{5}}-\frac{ψ^n}{\sqrt{5}}$

$\frac{ϕ^n}{\sqrt{5}}$ - $\frac{ψ^n}{\sqrt{5}} ≤ Fib(n) ≤ \frac{ϕ^n}{\sqrt{5}}+\frac{ψ^n}{\sqrt{5}}$

만약($\frac{ψ^n}{\sqrt{5}} ≤ 0.5$) 라면

$\frac{ϕ^n}{\sqrt5}-0.5$ $≤ Fib(n) ≤ \frac{ϕ^n}{\sqrt{5}}+0.5$를 만족한다.
그러므로 $\frac{ψ^n}{\sqrt{5}} ≤ 0.5$를 증명하면 $Fib(n)$은 $ϕ^n/\sqrt{5}$에 가장 가까운 수이다.

$\frac{ψ^n}{\sqrt{5}} ≤ 0.5$
$ψ^n ≤ \frac{\sqrt{5}}{2}$
$((1-\sqrt{5})/2)^n ≤ \frac{\sqrt{5}}{2}$

$\because -1<((1-\sqrt{5})/2)<1$이기 때문에,
$((1-\sqrt{5})/2)^1 ≤ \frac{\sqrt{5}}{2}$이라면,
$((1-\sqrt{5})/2)^n ≤ \frac{\sqrt{5}}{2}$이다.

$((1-\sqrt{5})/2) ≤ \frac{\sqrt{5}}{2}$
$1-\sqrt{5} ≤ \sqrt{5}$
$1 ≤ 2\sqrt{5}$
$∴ \frac{ψ^n}{\sqrt{5}} ≤ 0.5$

$∴$ $Fib(n)$은 $ϕ^n/\sqrt{5}$에 가장 가까운 정수이다.

난해한 글 읽어주셔서 감사합니다.