Question

(a) Find a closed-form solution for this recurrence relation: an=2⋅an−1−n+1 with a1=2a (b) Prove that your closed-form solution is correct.

Sequences
ANSWERED
asked 2021-01-31

(a) Find a closed-form solution for this recurrence relation: \(an=2\cdot an−1−n+1\) with \(a1=2a\)
(b) Prove that your closed-form solution is correct.

Answers (1)

2021-02-01

(a) Given \(an=(2an-1)-n+1\)
\(a1=2\)
Let us determine the first terms of the sequence until we notice a pettern:
\(a1=2=1+1\)
\(a2=2a1-2+1=2(2)-2=4-1=3=2+1\)
\(a3=2a2-3+1=2(3)-3=6-1=4=3+1\)
\(a4=2a3-4+1=2(4)-4=8-1=5=4+1\)
\(a5=2a4-5+1=2(5)-5=10-1=6=5+1\)
\(a6=2a5-6+1=2(6)-6=12-1=7=6+1\cdots\)
Thus we note that an=n+1 appears to hold in general.
(b) Given
\(an=(2an-1)-n+1\)
\(a1=2\)
To proof: \(an=n+1\) for all positive integers.
Proof by induction
Let P(n) be the statement \(an=n+1\)
Basis step \(n=1\)
\(an=a1=2\)
\(n+1=1+1=2\)
Thus P(1) is true
Inductive step Let P(k) be true.
\(ak=k+1\)
We need to proof that \(P(k+1)\) is true.
\(ak+1=2a((k+1)-1)-(k+1)+1 =(2ak)-k \)

\(=2(k+1)-k =2k+2-k =k+2 =(k+1)+1\)
Thus P(k+1) is true.
Conclusion By the principle of mathematical induction, P(n) is true for all positive integers n.

0
 
Best answer

expert advice

Have a similar question?
We can deal with it in 3 hours
...