千葉大学 理学研究科 基盤理学専攻 数学・情報数理学コース 2013年8月実施 専門 A5

标签：

• Recurrence-Relation
• Mathematical-Induction

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

次の Pascal プログラムについて答えよ。

function f(m, n: integer): integer;
begin
  if (m <= 0) or (n <= 0) then f := 1
  else if (m mod 2 = 0) then f := f(m-1,n)+f(m,n-1)
  else f := f(m-1,n)-f(m,n-1)
end;

(1) $f(2,5),f(3,4),f(3,5)$ を求めよ。(2) 任意の整数引数で実行が終了することを示せ。(3) 正の奇数 $m,n$ について $f(m,n)=0$ を示せ。(4) 任意の整数 $m,n$ について $f(m,n)=f(n,m)$ を示せ。

题目描述

给定上述 Pascal 递归程序。(1) 求 $f(2,5),f(3,4),f(3,5)$。(2) 证明对任意整数输入都终止。(3) 证明当 $m,n$ 均为正奇数时结果为 $0$。(4) 证明任意整数输入满足对称性 $f(m,n)=f(n,m)$。

Kai

(1)

$$\boxed{f(2,5)=3,\quad f(3,4)=3,\quad f(3,5)=0}.$$

(2)

非正の引数があれば直ちに終了する。両引数が正ならば、再帰呼び出しごとに正整数 $m+n$ が $1$ 減るため、無限に再帰することはない。

(3), (4)

$m,n\ge0$ に対して、次の公式を $m+n$ に関する帰納法で示す。

$$f(m,n)= \begin{cases} 0,&m,n\text{ がともに奇数},\\ \displaystyle\binom{\lfloor m/2\rfloor+\lfloor n/2\rfloor}{\lfloor m/2\rfloor},&\text{それ以外}. \end{cases}$$

$m=0$ または $n=0$ では両辺は $1$ である。$m=2a,n=2b$ では、帰納法の仮定とパスカルの公式から

$$f(2a,2b)=\binom{a+b-1}{a-1}+\binom{a+b-1}{a}=\binom{a+b}{a}.$$

$m=2a,n=2b+1$ では $f(2a-1,2b+1)=0$ より $f(2a,2b+1)=f(2a,2b)$。$m=2a+1,n=2b$ では $f(2a+1,2b-1)=0$ より $f(2a+1,2b)=f(2a,2b)$。最後に

$$f(2a+1,2b+1)=f(2a,2b+1)-f(2a+1,2b)=0.$$

よって公式が成立し、(3) を得る。また二項係数の対称性により (4) が成立する。負の引数を含む場合は両辺とも $1$ である。