Tuple cannot be accepted here unless the contents of the Tuple are all types.StringLiteral. Consider:

@njit
def foo():
    print('abcde'.startswith(('a', 1)))

foo()

it may be easier to just not accept Tuple to force type inference to try with a non-literal types instead.

I prefer to accept a UniTuple of UnicodeType, since it's more consistent with cpython. So I want to add a check to ensure the prefix type as expected. BTW, in your case:

@njit
def foo():
    print('abcde'.startswith(('a', 1)))

or another case:

prefix = ('a', 1)
@njit
def foo(prefix):
    print('abcde'.startswith(prefix))

Both ('a', 1) will be inferred as Tuple(unicode_type, int64), than Tuple containing a StringLiteral.
And in the executable case:

@njit
def foo():
    print('abcde'.startswith(('a', 'b')))

('a', 'b') will be inferred as UniTuple(unicode_type x 2), so I just have to ensure prefix is a UniTuple with unicode_type dtype. If I'm wrong, please point out with an example. I haven't found a counterexample...

BTW, I found an interesting thing in cpython (which I think we don't have to implement this short-cut strategy):

>>> 'a'.startswith(('a', 5))
True

>>> 'a'.startswith((1, 'a'))
Traceback (most recent call last):
  File "/Users/ld/opt/anaconda3/envs/numbaenv/lib/python3.10/code.py", line 90, in runcode
    exec(code, self.locals)
  File "<input>", line 1, in <module>
TypeError: tuple for startswith must only contain str, not int

Revised, please review this issue again. @stuartarchibald

By default, type inference will try using non-literal types first, and then if that fails, it will try again using literal types. Python source containing tuples of string literals will be inferred as types.Tuple(<types.StringLiteral>, <types.StringLiteral>, ...). e.g.

from numba import njit
import numpy as np

@njit
def foo():
    x = ('a', 'b')

foo()
foo.inspect_types()

You can see the "try non-literal then literal" types behaviour by doing something like:

from numba import njit, types
from numba.extending import overload
import numpy as np

def bar(tup):
    pass

@overload(bar)
def ol_bar(tup):
    print(f"bar:: tup type is {tup}")

@njit
def foo():
    x = ('a', 'b')
    bar(x)

foo()

(ignore the compilation error, just look at what gets printed to stdout).

RE: the 'a'.startswith(('a', 5)), there are implementation details like this in the CPython implementation. They don't need replicating unless there's some proven use case!