Java Reference
In-Depth Information
IN THEORY
7. 8
Prove by induction the formula
N
N
1
5
(
15
+
)
15
-
2
⎛
⎛
⎞
⎛
⎞
⎞
F
N
=
-
-------
---------------------
----------------
⎝
⎝
⎠
⎝
⎠
⎠
2
Prove the following identities relating to the Fibonacci numbers.
a.
b.
c.
d.
e.
f.
g.
7. 9
…
F
1
F
2
+++
F
N
=
F
N
2
-
1
+
…
F
1
F
3
+++
F
2
N
1
=
F
2
N
-
…
F
0
F
2
+++
F
2
N
=
F
2
N
1
-
1
+
F
N
-
F
N
1
=
F
1
F
2
F
2
F
3
()
-
1
+
F
2
N
+
…
+
+
+
F
2
N
-
F
2
N
=
F
2
2
…
F
1
F
2
F
2
F
3
+
+
+
F
2
N
F
2
N
1
=
F
2
N
1
-
1
2
+
+
F
2
+
F
N
1
=
F
2
N
1
2
+
+
Show that if
A
≡
B
(mod
N
) , then for any
C, D,
and
P,
the following are true.
a.
7. 1 0
A
+
C
≡
B
+
C
(mod
N
)
b.
AD
≡
BD
(mod
N
)
A
P
≡
B
P
(mod
N
)
c.
Prove that if
A
≥
B,
then
A
mod
B
<
A
/ 2. (
Hint:
Consider the cases
7. 1 1
B
A
/ 2 and
B
>
A
/ 2 separately.) How does this result show that the
running time of
gcd
is logarithmic?
≤
Prove by induction the formula for the number of calls to the recur-
sive method
fib
in Section 7.3.4.
7.12
Prove by induction that if
A
>
B
≥
0 and the invocation
gcd(a,b)
per-
7.13
forms
k
≥
1 recursive calls, then
A
≥
F
k
+ 2
and
B
≥
F
k
+ 1
.
Prove by induction that in the extended gcd algorithm,
XB
<
and
7. 1 4
YA
<
.
Write an alternative gcd algorithm, based on the following observa-
tions (arrange that
7. 1 5
AB
>
).
a.
gcd(
A, B
) = 2 gcd(
A
/2,
B
/ 2) if
A
and
B
are both even.
b.
gcd(
A, B
) = gcd(
A
/2,
B
) if
A
is even and
B
is odd.
c.
gcd(
A, B
) = gcd(
A, B
/ 2) if
A
is odd and
B
is even.
d.
gcd(
A, B
) = gcd((
A
+
B
) / 2, (
A
-
B
) / 2) if
A
and
B
are both odd.
Solve the following equation. Assume that
A
≥
1,
B
> 1, and
P
≥
0.
7. 1 6
T
(
N
) =
AT
(
N
/
B
) +
O
(
N
k
log
P
N
)
Search WWH ::
Custom Search