2.1.4 Recurrence Relation T(n)=2 T(n-1)+1 #4

@Joppan435:

Guys, I finally found out why he wrote ( (2^(k+1)) -1 ), instead of (2^k)-1.
So, let me make is as simple as possible, because I was also stuck on this very simple doubt for 2 hrs.

If we all got a doubt here, it clearly means that we did not count the number of terms. Let's take 2 cases first.
See this -> 2^(n-1) + 2^(n-2)+ . . . . . . . . + 2^(2) + 2^(1) + 2^(0).
This GP is from 0 to n-1, now, If i tell you to count from 0 to n-1 where n=4, you would totally count 4 digits.
That is 0 1 2 3. So there are 4 terms. Just like that for the above equation that I wrote, we have n terms.
So, now let's use that general GP formula that we all know about, that is  a(r^k-1)/(r-1).

You will get 2^n-1 as answer. BUT, BUT, BUT, We all want to know why on earth we all got 2^(k+1) - 1
right. It's really simple. Just like I told you that there are 2 cases. The 1st case was the first
equation that I asked you guys to count. Now, I will give you guys another equation as case 2. This
equation is the same equation that we will get exactly @10.06 which is 2^n + 2^(n-1) + 2^(n-2) + . . .
. . . . . . + 2^0. Now look at this equation really carefully and try to count how many terms there
are in this equation. It goes from 0 to n, and not from 0 to n-1(just like in case 1). So let me ask
you something, if I asked you to count from 0 to n, instead of n-1, where n=4, you will count 5 terms,
that is 0 1 2 3 4. which is n+1 and not n. NOW YOU GOT IT??. in case 2, you can see that there is a an
extra term called 2^n. That is the reason we take from 0 to n, instead of 0 to n-1. Instead of just
writing this as the next step of the GP equation substitution, he directly wrote it as ((2^(k+1))-1).
That was why we got confused.
I really hope this helped everything, as This took about 2 hrs. for me to find and come up with a explanation this detailed.

https://youtu.be/JvcqtZk2mng?list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O


Note:
https://chatgpt.com/c/3134e9e9-1fc7-42cc-ac34-3068b3dd1bdb
https://chatgpt.com/c/9d941785-d5a4-473f-89c9-0916aa955fc6
https://chatgpt.com/c/567a616f-4c2b-408b-a6d5-01372ab41c20  Explain 2^(n+1) = 2^n+2^n