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作业君