How can I make Mathematica return a series expansion in the form $\sum_{j=0}^\infty \dots$ instead of $a_0 + a_1x^1 + \dots + a_{n-1}x^{n-1}+ O(x^n)$

The following result is based on comments above exchanged between Michael E2 and me. Because

SeriesCoefficient[Sqrt[(x - t)^2 + c^2], {x, Infinity, n}]

returns unevaluated, and

SeriesCoefficient[Sqrt[u^2 + c^2], {u, Infinity, n}]
(* Piecewise[{{(c^2)^((1 + n)/2)*Binomial[1/2, -n/2], Mod[n, -2] == 0 && n <= 0}}, 0] *)

is manifestly incorrect (i.e., a bug), begin instead with

SeriesCoefficient[Sqrt[1 + z], {z, 0, n}];
s1 = %[[1, 1, 1]] (x - t) (c/(x - t))^(2 n)
(* (c/(-t + x))^(2 n) (-t + x) Binomial[1/2, n] *)

To test the correctness of this result, perform

Sum[s1, {n, 0, Infinity}] // Simplify
(* Sqrt[1 + c^2/(t - x)^2] (-t + x) *)

which is correct. However, it is not the desired result, because the terms are functions of x - t instead of x. So, expand s1 in t.

SeriesCoefficient[(t - x)^(1 - 2 n), {t, 0, m}, Assumptions -> n >= 0];
s2 = Simplify[%[[1, 1, 1]] s1 (t - x)^-(1 - 2 n), x - t > 0 && n ∈ Integers] t^m
(* c^(2 n) t^m (-x)^(-m - 2 n) x Binomial[1/2, n] Binomial[1 - 2 n, m] *)

Again, a test produces the correct result.

Sum[s2, {n, 0, Infinity}, {m, 0, Infinity}] // Simplify
(* Sqrt[1 + c^2/(t - x)^2] (-t + x) *)

Finally, all terms of a given order in x^-j must be summed to obtain the desired result. Doing so yields

f[j_] = Piecewise[{{x - t, j == 0}, {Sum[If[Mod[j + 1 - m, 2] == 0, 
    s2 /. x -> 1 /. n -> (j + 1 - m)/2, 0], {m, 0, j}] x^-j, j > 0}}];

To test its accuracy, compare it with the series expansion provided in the question.

Series[Sqrt[c^2 + (t - x)^2], {x, Infinity, 5}] // Normal
(* -t + (c^6 - 12 c^4 t^2 + 8 c^2 t^4)/(16 x^5) + (-3 c^4 t + 4 c^2 t^3)/(8 x^4) + 
   (-c^4 + 4 c^2 t^2)/(8 x^3) + (c^2 t)/(2 x^2) + c^2/(2 x) + x *)
FullSimplify[Sum[f[j], {j, 0, 5}] == %]
(* True *)

Thus, the sum of f[j] is the desired result.

All calculations were performed with

$Version
(* 11.1.0 for Microsoft Windows (64-bit) (March 13, 2017) *)

SeriesCoefficient will work if one adjusts the expression so that it is finite as x->Infinity. So:

nthTerm = SeriesCoefficient[Sqrt[c^2+(t-x)^2]/x,{x,Infinity,n},Assumptions->n>=0];
nthTerm //InputForm

(*
DifferenceRoot[Function[{\[FormalY], \[FormalN]}, 
{(-1 + \[FormalN])*(c^2 + t^2)*\[FormalY][\[FormalN]] + (-t - 2*\[FormalN]*t)*\[FormalY][1 + \[FormalN]] + 
  (2 + \[FormalN])*\[FormalY][2 + \[FormalN]] == 0, \[FormalY][0] == 1, \[FormalY][1] == -t}]][n]
*)

Hence, the desired sum is:

sum[t_] := Inactive[Sum][nthTerm x^(1-n), {n, 0, t}]
sum[Infinity] //InputForm

(*
Inactive[Sum][x^(1 - n)*DifferenceRoot[Function[{\[FormalY], \[FormalN]}, 
 {(-1 + \[FormalN])*(c^2 + t^2)*\[FormalY][\[FormalN]] + (-t - 2*\[FormalN]*t)*\[FormalY][1 + \[FormalN]] + 
    (2 + \[FormalN])*\[FormalY][2 + \[FormalN]] == 0, \[FormalY][0] == 1, \[FormalY][1] == -t}]][n], {n, 0, Infinity}]
*)

Check:

Series[expr, {x, Infinity, 5}]//TeXForm

$x-t+\frac{c^2}{2 x}+\frac{c^2 t}{2 x^2}+\frac{4 c^2 t^2-c^4}{8 x^3}+\frac{4 c^2 t^3-3 c^4 t}{8 x^4}+\frac{c^6-12 c^4 t^2+8 c^2 t^4}{16 x^5}+O\left(\left(\frac{1}{x}\right)^6\right)$

Series[Activate@sum[6], {x, Infinity, 5}]//TeXForm

$x-t+\frac{c^2}{2 x}+\frac{c^2 t}{2 x^2}+\frac{\frac{c^2 t^2}{2}-\frac{c^4}{8}}{x^3}+\frac{\frac{c^2 t^3}{2}-\frac{3 c^4 t}{8}}{x^4}+\frac{c^6-12 c^4 t^2+8 c^2 t^4}{16 x^5}+O\left(\left(\frac{1}{x}\right)^6\right)$

Still another approach is to use FindSequenceFunction, which should work whenever the series coefficients satisfy a recurrence relation that is not too complicated. Begin by obtaining the list of coefficients of the series.

coef = Series[Sqrt[c^2 + (t - x)^2], {x, Infinity, 8}][[3]]
(* {1, -t, c^2/2, (c^2 t)/2, 1/8 (-c^4 + 4 c^2 t^2), 1/8 (-3 c^4 t + 4 c^2 t^3), 
    1/16 (c^6 - 12 c^4 t^2 + 8 c^2 t^4), 1/16 (5 c^6 t - 20 c^4 t^3 + 8 c^2 t^5), 
    1/128 (-5 c^8 + 120 c^6 t^2 - 240 c^4 t^4 + 64 c^2 t^6), 
    1/128 (-35 c^8 t + 280 c^6 t^3 - 336 c^4 t^5 + 64 c^2 t^7)} *)

Then apply FindSequenceFunction and, since the result is a DifferenceRoot, discard any superfluous initial conditions.

FindSequenceFunction[coef];
ReplacePart[%, {1, 2} -> %[[1, 2, 1 ;; 3]]]
(* DifferenceRoot[Function[{\[FormalY], \[FormalN]}, {(-2 + \[FormalN]) (c^2 + t^2) 
   \[FormalY][\[FormalN]] + (t - 2 \[FormalN] t) \[FormalY][1 + \[FormalN]] 
   + (1 + \[FormalN]) \[FormalY][2 + \[FormalN]] == 0, 
   \[FormalY][1] == 1, \[FormalY][2] == -t}]] *)

Not surprisingly, this result is equivalent to that in the earlier answer by Carl Woll. It is validated by

Simplify[Table[%[n], {n, 10}] == coef]
(* True *)