ウォンツテック

そでやまのーと

■

SICP SICP

もはや数学

問題1.11

f(n) = \left\{  n \text{ if }n<3 \\{f(n-1)+2f(n-2)+3f(n-3)} \text{ if }n\geq3\right.

再帰的プロセス

(define (func n)
  (cond ((< n 3) n)
        (else (+ (func (- n 1)) 
                 (* 2 (func (- n 2)))
                 (* 3 (func (- n 3))))

反復的プロセス

思考
３つの整数a, b, cを初期値をf(2), f(1), f(0)で初期化し、
a ← a + 2b + 3c
b ← a
c ← b
の変換を繰り返すとn回後にはa,b,cはそれぞれf(n+2), f(n+1), f(n)に等しい

(define (f n)
  (f-iter 2 1 0 n))
(define (f-iter a b c count)
  (if (= count 0)
      c
      (f-iter (+ a (* 2 b) (* 3 c)) a b)))

問題1.12

(define (pascal n m)
  (cond ((= m 1) 1)
        ((= m n) 1)
        (else (+ (pascal (- n 1) (- m 1))
                 (pascal (- n 1) m)))))

問題1.13

fib(n) = fib(n-1) + fib(n-2) ...①

まず\psi = (1-\sqrt5)/2とする時
fib(n) = (\phi^n - \psi^n)/\sqrt5 ...②
である事を数学的帰納法で証明する

n=1の時
(\phi - \psi)/\sqrt5 = 1
より②が成り立つ
n\leq kの時②が成り立つとすると
fib(k+1) = fib(k) + fib(k-1) ※①のfibの定義より
         = (\phi^k - \psi^k)/\sqrt5 + (\phi^{k-1} - \psi^{k-1})/\sqrt5 ※仮定より
         = \phi^{k-1}(\phi+1)/\sqrt5 - \psi^{k-1}(\psi+1)/\sqrt5
ここで
 \phi^2 = \phi + 1,  \psi^2 = \psi + 1
より
fib(k+1) = (\phi^{k+1} - \psi^{k+1})/\sqrt5
となるので仮定はn=k+1の時にも成り立つ。
以上より数学的帰納法により②は全ての自然数nで成り立つ。


次に
|\psi^n/\sqrt5| < 1/2 ( n \geq 1) ...③
を数学的帰納法で証明する
n=1の時
|\psi/\sqrt5| = |(1-\sqrt5)/2\sqrt5)|
              = 1/2 - 1/2\sqrt5
              < 1/2
成り立つ
n=kの時成り立つと仮定すると
|\psi^{k+1}/\sqrt5| = |\psi||\psi^k/\sqrt5|
                    < |\psi|/2
                    = (\sqrt5 - 1)/4
                    < (3 - 1)/4
                    = 1/2
によりn=k+1の時も成り立つ
よって仮定は全ての自然数nで成り立つ。

②と③より
|fib(n) - \phi^n/\sqrt5| = |\psi^n/\sqrt5|
                         < 1/2
となりfib(n)が\phi^n/\sqrt5に最も近い整数となる。
※実数rに対してもっとも近い整数mとは


    

    r-m
    <1/2
    


となる整数の事である。