Female and Male Sequences

Julia, 52 48 bytes

x->[n÷φ|(5n^2|4∈(2:3n).^2)for| =(+,-),n=1:x]

Try it online!

Background

In On Hofstadter's married functions, the author shows that

where φ denotes the golden ratio,

and F_n denotes the n^th Fibonacci number.

Furthermore, in Advanced Problems and Solutions, H-187: Fibonacci is a square, the proposer shows that

where L_n denotes the n^th Lucas number, and that – conversely – if

then n is a Fibonacci number and m is a Lucas number.

From this, we deduce that

whenever n > 0.

How it works

Given input x, we construct a 2 by x matrix, where | is addition in the first column and subtraction in the second, and n iterates over the integers between 1 and x in the rows.

The first term of both F(n - 1) and M(n - 1) is simply n÷φ.

We compute δ(n) and ε(n) by calculating 5n² | 4 and testing if the result belongs to the array of squares of the integers between 2 and 3n. This tests both for squareness and, since 1 is not in the range, for n > 1 if | is subtraction.

Finally we add or subtract the Boolean resulting from 5n^2|4∈(2:3n).^2 to or from the previously computed integer.

Python 2, 79 70 bytes

a=0,;b=1,
exec"a,b=b,a+(len(a)-b[a[-1]],);"*~-input()*2
print b,'\n',a

Iterative rather than recursive, because why not. The first line has a trailing space - if that's not okay it can be fixed for an extra byte. -9 bytes thanks to @Dennis.

Here are some combined lambdas which didn't really help:

f=lambda n,k:n and n-f(f(n-1,k),k^1)or k
f=lambda n,k:[k][n:]or f(n-1,k)+[n-f(f(n-1,k)[-1],k^1)[-1]]

Both take n and a parameter k either 0 or 1, specifying male/female. The first lambda returns the nth element, and the second lambda returns the first n elements (with exponential runtime).

MATL, 23 bytes

1Oiq:"@XJth"yy0)Q)_J+hw

Try it online!

Explanation

This works iteratively. Each sequence is kept in an array. For each index n the new term of each sequence is computed and attached to the corresponding array. A for loop with N−1 terms is used, where N is the input number.

The update for sequence M needs to be done first. This is because sequence F is always greater than or equal to sequence M for the same index, so if we tried to update F first we would need a term of M not computed yet.

The two update equations are the same interchanging F and M. Thus the code for the updating is reused by applying a for loop with two iterations and swapping the sequences in the stack.

1        % Push 1: seed for F sequence
O        % Push 0: seed for M sequence
iq:      % Input N. Generate range [1 2 ... N-1]
"        % For each (i.e. iterate N-1 times)
  @      %   Push current index, n (starting at 1 and ending at N-1)
  XJ     %   Copy to clipboard J
  th     %   Duplicate and concatenate. This generates a length-2 array
  "      %   For each (i.e. iterate twice)
    yy   %   Duplicate top two elements, i.e. F and M sequences
    0)   %     In the *first* iteration: get last entry of M, i.e M(n-1)
    Q)   %     Add 1 and index into F. This is F(M(n-1))
    _J+  %     Negate and add n. This is n-F(M(n-1)), that is, M(n)
    h    %     Concatenate to update M
    w    %     Swap top two elements, to bring F to top.
         %     In the *second* iteration the procedure is repeated to update F,
         %     and then the top two elements are swapped to bring M to top again,
         %     ready for the next iteration of the outer loop
         %   End for implicitly
         % End for implicitly
         % Display implicitly from bottom to top: first line is F, second is M