$\sum_{i=0}^{k-1} 2^{\lfloor{i/2}\rfloor} = 2 * (2^{k/2}-1)$ when k is even
$\sum_{i=0}^{k-1} 2^{\lfloor{i/2}\rfloor} = 3 * 2^{(k-1)/2}-2$ when k is odd
How can I solve this by induction or derive the RHS from LHS? One possible approach was to consider even, and odd cases as 2m and (m-1)/2 without the floor, but the RHS I got was different.
A good research paper I found on resizable arrays for context: https://www.researchgate.net/publication/2801681_Resizable_Arrays_in_Optimal_Time_and_Space
As was said, in these kind of problems, it pays to consider even and odd values separately.
Let $f(k) =\sum_{i=0}^{k-1} 2^{\lfloor{i/2}\rfloor} $. Then
$\begin{array}\\ f(2k) &=\sum_{i=0}^{2k-1} 2^{\lfloor{i/2}\rfloor}\\ &=\sum_{i=0}^{k-1} (2^{\lfloor{2i/2}\rfloor}+2^{\lfloor{(2i+1)/2}\rfloor})\\ &=\sum_{i=0}^{k-1} (2^{i}+2^{i})\\ &=2\sum_{i=0}^{k-1} 2^{i}\\ &=2(2^k-1)\\ \end{array} $
and $f(2k+1) =f(2k)+2^k =2(2^k-1)+2^k =3(2^k)-2 $.
Since $k =\dfrac{2k}{2} =\lfloor\dfrac{2k+1}{2}\rfloor $, you get the specified formulas.