Suppose we have a non-negative sequence $\{a_j\}$ such that $\sum_{j=1}^{\infty}a_j<L<\infty$ for some finite constant $L$. My professor claims $$\sum_{j=k}^{\infty} a_j =O(\log^{-1} k)$$ but I am not sure how to derive this. I know $\sum_{j=k}^{\infty} \frac{1}{j^p} = O(k^{1-p})$ for $p>1$, and my handwaving answer is that $k^{1-p}$ has the same growth as $\frac{1-p}{k^{p-1}-1}$, so taking $p\to 1$ and applying L'Hopital we get that the tail for any convergent series has to be bounded by $\log^{-1}(k)$ but for this to work I think I would have to show $a_j= O(\frac{1}{j^p})$ for some $p>1$.
My professor suggested using that $a_j =O(\frac{1}{j \log j})$, but I don't know what I am supposed to use this for since the sum of $\frac{1}{j \log j}$ is divergent. If I could show there exists some $\delta>0$ for which $a_j =O(\frac{1}{j^{1+\delta} \log j})$, then I can show the claim with an integral comparison.
He also said this bound wasn't tight, so any suggestions on possible tighter bounds would be great!
That claim is wrong. The series remainder $\sum_{j=k}^{\infty} a_j$ of a converging series $\sum_{j=1}^{\infty}a_j$ converges to zero, but that convergence can be arbitrarily slow. Requiring that all $a_j$ are non-negative does not change that fact.
Let $(r_k)$ be an arbitrary decreasing sequence of real numbers with $r_k\to 0$ and set $a_j = r_j - r_{j+1}$. Then $a_j \ge 0$ and $$ \sum_{j=1}^n a_j = r_1 - r_{n+1} \, , $$ so that $\sum_{j=1}^\infty a_j = r_1 < L := r_1 + 1$. But the series remainder $$ \sum_{j=k}^{\infty} a_j = r_k $$ can decrease to zero as slowly as you like.
For a concrete counterexample one can choose $r_k = f(k)$ with $$ f(x) = \frac{\log(e + \log x)}{e + \log x} $$ which is decreasing on $[1, \infty)$ with $\lim_{x \to \infty}\log(x)\cdot f(x) = +\infty$.