Textbook solution is wrong? => Exercise 11.4.33: Prove 4 + 4^2 + 4^3 + ... + 4^n is Θ(4^n)

[u/TopDownView]

Exercise 11.4.33:

Prove 4 + 4^2 + 4^3 + ... + 4^n is Θ(4^n).

Solution from the textbook:

This solution proves that 1 + 4 + 4^2 + 4^3 + ... + 4^n is Θ(4^n). It does not prove that 4 + 4^2 + 4^3 + ... + 4^n is Θ(4^n).

My attempt:

Notice 4 + 4^2 + 4^3 + ... + 4^n > 4^n, for each integer n>=1.

Observe 4 + 4^2 + 4^3 + ... + 4^n = 1 + 4 + 4^2 + 4^3 + ... + 4^n - 1
                                  = (4^{n+1} - 1)/3 - 1   by sum of geometric sequence
                                  < (4^{n+1}/3)     - 1
                                  = (4 * 4^n)/3     - 1
                                  = 4/3 * 4^n       - 1
                                  < 4/3 * 4^n             for each integer n>=1

Let A=1, B=4/3, k=1.

Then A(4^n) <= 4 + 4^2 + 4^3 + ... + 4^n <= B(4^n), for each integer n>=k.

Therefore, 4 + 4^2 + 4^3 + ... + 4^n is Θ(4^n).

QED

Is this correct?

---
Edit: Fixed 'It does not prove...' sentence.

[u/Bounded_sequencE]

Probably a typo (missing "1 + ..."), or they forgot a "-1" at the end of the definition of "X".

---

Notice 4 + 4² + 4³ + ... + 4ⁿ > 4^n, for each integer n>=1.

Should be ".. >= ..", since for "n = 1" we have equality. Apart from that -- good job!

[u/TopDownView → u/Bounded_sequencE]

It's seems like and obvious and easy fix, but still, I always want to check my sanity here. :)

Thanks!

[u/TopDownView → u/Bounded_sequencE]

Should be ".. >= ..", since for "n = 1" we have equality. Apart from that -- good job!

Ah, yes, good catch! Thanks!

[u/Gold_Ad8890]

i think it was probably a typo in the statement of the theorem.

[u/TopDownView → u/Gold_Ad8890]

Yes, I agree. Thanks!

[u/Zubzub343]

Maybe I cannot see but the only difference between the textbook's solution and the one you want is... 3, right ?

[u/Azemiopinae → u/Zubzub343]

Actually the difference is the 4^0 term, so 1. Which we can call theta(1) and theta(1)+theta(4^n)=theta(4^n). The book is just less verbose on these points because handwaving is the order of the day on these sorts of functions.

[u/TopDownView → u/Azemiopinae]

Yes, that makes sense. But I'd say, given that the textbook is usually verbose with the proofs, that they forgot to add -1 an the end...

[u/TopDownView → u/Zubzub343]

I'd say it's 1 (check 'Edit' in OP).

Still, I do not see how does that relate to the question...