程序代写案例-S0

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top
Exercise 2.13
We are tasked to use the repertoire method to find a closed form for
∑n
k=0(−1)kk2. We can rewrite this
as a recurrent sequence
S0 = 0
Sn = Sn−1 + (−1)nn2.
To solve this using the repertoire method, we start with the following more general recurrence
R0 = α
Rn = Rn−1 + (−1)n
(
β + γn+ δn2
)
.
Note that the a general solution to Rn includes a solution to Sn as a special case (we set (α, β, γ, δ) = (0, 0, 0, 1)).
The general solution to this will be of the form
Rn = A(n)α+B(n)β + C(n)γ +D(n)δ.
We will use the following general FACT: If a polynomial equation akn
k + ak−1nk−1 + · · ·+ a1n+ a0 = 0 has
more than k many solutions, then all of the coefficients ak, . . . , a1, a0 are equal to 0.
Let us build our repertoire.
• We guess that Rn = 1 and look for α, β, γ, δ that guarantee this condition holds. We calculate that
1 = R0 = α
1 = R2n = R2n−1 + (−1)2n(β + γ(2n) + δ(2n)2)
= 1 + β + 2γn+ 4n2δ, therefore
0 = β + 2γn+ 4n2δ,
The last equation holds for infinitely many n, so our fact implies that β = γ = δ = 0. Putting this
together, we have that Rn = 1 when (α, β, γ, δ) = (1, 0, 0, 0). This means that A(n) = 1.
• We guess that Rn = (−1)n and look for α, β, γ, δ that guarantee this condition holds. We calculate
that
(−1)0 = R0 = α
(−1)n = Rn = Rn−1 + (−1)n(β + γn+ δn2)
= (−1)n−1 + (−1)n(β + γn+ δn2), therefore
0 = −2 + β + γn+ n2δ.
The last equation holds for infinitely many n, so our fact implies that β− 2 = γ = δ = 0. Putting this
together, we have that Rn = (−1)n when (α, β, γ, δ) = (1, 2, 0, 0), and hence A(n) + 2B(n) = (−1)n.
• We guess that Rn = (−1)nn and look for α, β, γ, δ that guarantee this condition holds. We calculate
that
(−1)0(0) = R0 = α
(−1)nn = Rn = Rn−1 + (−1)n(β + γn+ δn2)
= (−1)n−1(n− 1) + (−1)n(β + γn+ δn2), therefore
n = −(n− 1) + β + γn+ n2δ, so
0 = (β + 1) + (γ − 2)n+ δn2.
The last equation holds for infinitely many n, so our fact implies that β + 1 = γ − 2 = δ = 0.
Putting this together, we have that Rn = 1 when (α, β, γ, δ) = (0,−1, 2, 0), and hence
(1) −B(n) + 2C(n) = (−1)nn
1
• We guess that Rn = (−1)nn2 and look for α, β, γ, δ that guarantee this condition holds. We calculate
that
(−1)0(0) = R0 = α
(−1)nn2 = Rn = Rn−1 + (−1)n(β + γn+ δn2)
= (−1)n−1(n− 1)2 + (−1)n(β + γn+ δn2), therefore
n2 = −(n− 1)2 + β + γn+ n2δ, so
0 = (β − 1) + (γ + 2)n+ (δ − 2)n2.
The last equation holds for infinitely many n, so our fact implies that β − 1 = γ + 2 = δ − 2 = 0.
Putting this together, we have that Rn = 1 when (α, β, γ, δ) = (0, 1,−2, 2), and hence
B(n)− 2C(n) + 2D(n) = (−1)nn2.
We get the following utilizing equation 1 (the third piece from our repertoire).
B(n)− 2C(n) + 2D(n) = (−1)nn2
2D(n) = (−1)nn2 −B(n) + 2C(n)
= (−1)nn2 + (−1)nn
= (−1)n (n2 + n)
D(n) = (−1)nn
2 + n
2
We noticed at the outset that D(n) is the closed form for the sum we were initially investigating, so
we’re done.
Exercise 2.19
Use a summation factor for the following recurrence
T0 = 5
2Tn = nTn−1 + 3n! for n > 0.
In this problem, we have an = 2, bn = n, and cn = 3n!. This means that we have the following for
sn.
sn =
an−1 · · · a1
bn · · · b2
=
2n−1
n!
2
So for Tn, we get that
Tn =
1
snan
(
s1b1T0 +
n∑
k=1
skck
)
=
n!
2n
(
1 · 1 · 5 +
n∑
k=1
2n−1
n!
(3n!)
)
=
n!
2n
(
5 +
n∑
k=1
3 · 2n−1
)
=
n!
2n
(
5 + 3
2n − 1
2− 1
)
=
n!
2n
(5 + 3 (2n − 1))
=
n!
2n
(5 + 3 · 2n − 3)
=
n!
2n
(3 · 2n + 2)
= 3n! +
n!
2n−1
Exercise 2
T0 = 0
Tn = n− 1 + 2
n
n−1∑
k=0
Tk for n > 0.
Tn = n− 1 + 2
n
n−1∑
k=0
Tk
nTn = n(n− 1) + 2
n−1∑
k=0
Tk
(n− 1)Tn−1 = (n− 1)(n− 2) + 2
n−2∑
k=0
Tk for n > 1, so
nTn − (n− 1)Tn−1 = (n− 1)(n− (n− 2)) + 2Tn−1
nTn = (n+ 1)Tn−1 + 2(n− 1) for n > 1.
Notice that the last line is true for n = 1 also, so we are now looking at the equivalent recurrence
T0 = 0
nTn = (n+ 1)Tn−1 + 2(n− 1) for n > 0.
This recurrence admits analysis via a summation factor, with an = n, bn = n + 1, and cn = 2(n − 1),
which means we have the following for s(n).
3
s(n) =
an−1 · · · a1
bn · · · b2
=
(n− 1) · · · 1
(n+ 1) · · · 3
=
2
n(n+ 1)
Hence, we have for Tn
Tn =
1
snan
(
s1b1T0 +
n∑
k=1
skck
)
=
n+ 1
2
(
2
2
(2)(0) +
n∑
k=1
4(k − 1)
k(k + 1)
)
=
n+ 1
2
(
4
n∑
k=1
k − 1
k(k + 1)
)
= 2(n+ 1)
n∑
k=1
(
1
k + 1
− 1
k(k + 1)
)
= 2(n+ 1)
(
n+1∑
k=2
1
k

n∑
k=1
(
1
k
− 1
k + 1
))
= 2(n+ 1)
((
Hn − 1 + 1
n+ 1
)

(
1− 1
n+ 1
))
= 2(n+ 1)
(
Hn − n
n+ 1
− n
n+ 1
)
= 2(n+ 1)Hn − 4n
4

欢迎咨询51作业君
51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468