Discrete Mathematics · Induction, recursion, and invariants

(Honors) Let u_n be defined by u_0=0, u_1=1, and u_n=4u_(n-1)-4u_(n-2)+n for n≥ 2

Problem

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

Hint

The homogeneous characteristic polynomial has a double root at $2$, which is why the exponential piece is linear-times-$2^n$; the inhomogeneous term is linear, and $1$ 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.

Check your answer See the full 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.

Problem

Hint

Check your work

More Discrete Mathematics practice problems