I'm trying to show that $n$ append operations on a dynamic array run in $O(n)$ time for the growing strategy of allocating an array of capacity $N+\lceil\frac{N}{4}\rceil$ when the old array of capacity $N$ is full. I want to use both the aggregate analysis and the accounting method (Explanation).
I'm assuming that a single append has a cost of 1 "coin", and copying $m$ elements into a new array costs $m$ coins.
My argumentation for the accounting method is as follows: Suppose the array's capacity is $N$ and the array has just expanded from its previous capacity of $N'$, thus $N=N'+\lceil\frac{N'}{4}\rceil$. The next resize will require $N$ coins to pay for it and we have $\lceil\frac{N'}{4}\rceil$ appends to save enough coins. With $c$ denoting the amount of coins we need to save per append, we have to make sure that $\lceil\frac{N'}{4}\rceil*c\geq N$: $$\lceil\frac{N'}{4}\rceil*c\geq N\implies\lceil\frac{N'}{4}\rceil*c\geq N'+\lceil\frac{N'}{4}\rceil \implies c\geq\frac{N'+\lceil\frac{N'}{4}\rceil}{\lceil\frac{N'}{4}\rceil}=\frac{N'}{\lceil\frac{N'}{4}\rceil}+1$$ Since for $\forall N'\in\mathbb N$ $$\frac{N'}{\lceil\frac{N'}{4}\rceil}\leq4,$$ (How do I show this property? I've just gone with the limit of this fraction and failed to show it via induction.)
we can set $$c=5=4+1\geq\frac{N'}{\lceil\frac{N'}{4}\rceil}+1.$$ Now, by assigning a cost of 6 coins to every append (one coin extra for the append itself), we can calculate the total amortized cost $\hat T$ of $n$ append operations as $\hat T(n)=6n$. Given that the actual costs $T$ are always less than or equal to the amortized costs $\hat T$, we have found an upper bound that is $O(n)$.
Moving to the aggregate analysis, I'm starting to struggle. The array’s initial capacity is $k$, and I'm using $N+\lceil\frac{N}{4}\rceil=\lceil1.25*N\rceil$. I have to find an upper bound for the sum $$T(n)=1+...+1+k+1+...+1+\lceil1.25*k\rceil+1+...+1+\lceil1.25*\lceil1.25*k\rceil\rceil+...+???$$ We have $n$ ones for the $n$ appends, but I don't know how to find the sum of the terms that account for the resize operations, as the nested ceilings are throwing me off. How can I handle those terms?