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

标签：

• 递归
• 数学归纳法

Author

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

Description

$\mathbb N=\{0,1,2,\ldots\}$ とし、次の式で $f:\mathbb N^2\to\mathbb N$ を定める。

$$f(0,y)=y+1,\qquad f(x+1,0)=f(x,1),\qquad f(x+1,y+1)=f(x,f(x+1,y)).$$

(1) 全ての $x,y$ について値が一意に定義されることを示せ。

(2) $f(2,y)=2y+3$ を示せ。

(3) $f(3,y)$ を四則と冪で表せ。

(4) $x+y+1\le f(x,y)$ を示せ。

题目描述

令 $\mathbb N$ 包含零，按下式定义函数：

$$f(0,y)=y+1,\quad f(x+1,0)=f(x,1),\quad f(x+1,y+1)=f(x,f(x+1,y)).$$

(1) 证明每对 $x,y$ 的函数值均存在且唯一。

(2) 证明 $f(2,y)=2y+3$。

(3) 用四则运算和幂表示 $f(3,y)$。

(4) 证明 $f(x,y)\ge x+y+1$。

Kai

(1)

$x$ に関する帰納法を用いる。$x=0$ の行は全て定まっている。$f(x,y)$ が全ての $y$ について一意に定まったとすると、$f(x+1,0)=f(x,1)$ が定まる。その後は $y$ に関する帰納法で $f(x+1,y+1)=f(x,f(x+1,y))$ が一意に定まる。よって全域で一意に定義される。

(2)

$f(1,0)=2$、$f(1,y+1)=f(1,y)+1$ より $f(1,y)=y+2$。従って

$$f(2,0)=3,\qquad f(2,y+1)=f(2,y)+2,$$

なので $f(2,y)=2y+3$。

(3)

$f(3,0)=5$、$f(3,y+1)=2f(3,y)+3$。$b_y=f(3,y)+3$ とおけば $b_0=8,b_{y+1}=2b_y$ なので

$$f(3,y)=2^{y+3}-3.$$

(4)

再び $x$ に関する帰納法を用いる。$x=0$ では等号。第 $x$ 行で成立すると仮定すると、

$$f(x+1,0)=f(x,1)\ge x+2.$$

さらに $f(x+1,y)\ge x+y+2$ を仮定すれば

$$f(x+1,y+1)=f(x,f(x+1,y))\ge x+f(x+1,y)+1\ge2x+y+3\ge x+y+3.$$

内側の帰納法と合わせて、全ての $x,y$ で成立する。