Skip to main content

Discrete Mathematics · Induction, recursion, and invariants

(Honors) Let uₙ be defined by u₀=0, u₁=1, and uₙ=4uₙ₋₁-4uₙ₋₂+n for n ≥ 2

Problem

Discrete Mathematics practice problem

(Honors) Let unu_n be defined by u0=0u_0=0, u1=1u_1=1, and un=4un−1−4un−2+nu_n=4u_{n-1}-4u_{n-2}+n for n≥2n\geq 2. First find constants A,B,C,DA,B,C,D such that the formula un=(A+Bn)2n+Cn+Du_n=(A+Bn)2^n+Cn+D holds for n=0n=0 and n=1n=1 and is consistent with the recurrence for n≥2n\geq 2. Then prove by strong induction that your closed form is valid for every integer n≥0n\geq 0.

Hint

Hint

The homogeneous characteristic polynomial has a double root at 22, which is why the exponential piece is linear-times-2n2^n; the inhomogeneous term is linear, and 11 is not a homogeneous root, so a linear particular solution is the right guess.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Discrete Mathematics sample problem: Try the free sample problem.

More Discrete Mathematics practice problems

Back to Discrete Mathematics

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.