-
Notifications
You must be signed in to change notification settings - Fork 13
/
chap3.html
55 lines (55 loc) · 1.65 KB
/
chap3.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
<html>
<head>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript">
</script>
</head>
<body>
<h2>
Exercise 3.7
</h2>
<h3>
Recurrence:
</h3>
<p>
\(X_n=n,\text{ for } 0\le n< m \\
X_n=X_{n-m}+1,\text{ for } n\ge m\)
</p>
<h3>
Closed Form Hypothesis:
</h3>
<p>
\(X_n=\lfloor n/m\rfloor+n\text{ mod } m \\
X_n=\lfloor n/m \rfloor+n-m\lfloor n/m\rfloor \\
X_n=n-(m-1)\lfloor n/m\rfloor\)
</p>
<h3>
Inductive Proof:
</h3>
<p>
\(X_0=0-(m-1)\lfloor 0/m\rfloor=0 \\
\lfloor n/m\rfloor=0,\text{ for } 0\le n< m \\
X_n=0+n-m(0)=n,\text{ for } 0\le n< m \\
X_n=n-m-(m-1)\lfloor(n-m)/m\rfloor+1,\text{ for } n\ge m \\
X_n=n-m-(m-1)\lfloor n/m\rfloor+(m-1)+1,\text{ for } n\ge m \\
X_n=n-(m-1)\lfloor n/m\rfloor,\text{ for } n\ge m \)
</p>
<h2>
Exercise 3.10
</h2>
<h3>
Show \(\lceil\frac{2x+1}2\rceil-\lceil\frac{2x+1}4\rceil+\lfloor\frac{2x+1}4\rfloor\)
is always \(\lfloor x\rfloor\) or \(\lceil x\rceil\)
</h3>
<p>
\(
-\lceil y\rceil + \lfloor y\rfloor=-1,\text{ for } y \notin \Bbb Z\\
-\lceil y\rceil + \lfloor y\rfloor=0,\text{ for } y \in \Bbb Z \\
\frac{2x+1}2=0 \implies \frac{2x+1}2 \in \{1.5, 3.5, 5.5,...\} \\
\{x\}<0.5 \implies \lfloor x\rfloor \\
\{x\}>0.5 \implies \lceil x\rceil \\
\{x\}=0.5\text{ and }[\lfloor x \rfloor\text{ is even}] \implies \lfloor x\rfloor \\
\{x\}=0.5\text{ and }[\lfloor x \rfloor\text{ is odd}] \implies \lceil x\rceil
\)
</p>
</body>
<html>