You pretty much got it, although the analysis becomes a lot simpler if you consider evaluating the generating function in base b by substituting x = b. I'll use multiples of 10 here for visual understanding:

    >>> import decimal
    >>> decimal.getcontext().prec = 50
    >>> b = decimal.Decimal(10**3)
    >>> b/(b**2 - b - 1)
    Decimal('0.0010010020030050080130210340550891442333776109885996')

For a large enough b we don't have to worry of overflow from the next terms. So then we can shift k terms, mod b to get rid of the earlier terms, and floor to get rid of (the infinite) later terms:

    >>> k = 6
    >>> b**k * b/(b**2 - b - 1)
    Decimal('1001002003005008.0130210340550891442333776109885996')
             ^^^^^^^^^^^^^    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                mod b                       floor

So for any sufficiently large b we have floor(b^(k+1)/(b^2 - b - 1)) % b. And if we let b = 2^(k+c) for a sufficiently large constant c we use asymptotics to find that this is a sufficiently large b for large k, and check the first couple numbers to find that b = 2^(k+1) works.