[Question]
  [
Given a positive integer input **N**, output the two non-negative numbers, **a** and **b**, where **a < b**, with the lowest possible mean value that will result in the number **N** being part of the recurring relation sequence:
```
f(0) = a
f(1) = b
f(n) = f(n-2)+f(n-1)
```
~~In case there are more than one solution where the mean of **a** and **b** are minimal, then you should output the one with the lowest **b**.~~ Proof that this is not possible is provided by [cardboard\_box](https://codegolf.stackexchange.com/a/147843/31516).
Your can assume **N** is within the representative range of integers in your language / system.
### Test cases
```
N = 1
a = 0, b = 1
N = 15
a = 0, b = 3
N = 21
a = 0, b = 1
N = 27
a = 0, b = 9   <- Tricky test case. [3, 7] is not optimal and [4, 3] is not valid
N = 100
a = 4, b = 10
N = 101
a = 1, b = 12
N = 102
a = 0, b = 3
N = 1000
a = 2, b = 10
```
  
[Answer]
# [Husk](https://github.com/barbuz/Husk), ~~19~~ ~~18~~ ~~16~~ ~~14~~ ~~13~~ 15 bytes
Thanks Zgarb for saving 1 byte.
```
ḟö£⁰ƒẊ++ÖΣṖ2Θḣ⁰
```
[Try it online!](https://tio.run/##yygtzv7//@GO@Ye3HVr8qHHDsUkPd3Vpax@edm7xw53TjM7NeLgDJPz//38jcwA "Husk – Try It Online")
### Explanation:
**Disclaimer:** I really don't understand the `ȯƒẊ++` section of the code.
Edit: It appears to translate to the Haskell `fix.(mapad2(+).).(++)`, where `mapad2` is apply function to all adjacent pairs in a list. (Although, knowing Husk, in the context of this program it could mean something else)
```
            Θḣ⁰    Create the list [0..input]
          Ṗ2       Generate all possible sublists of length 2
        ÖΣ         Sort them on their sums
ḟ                  Find the first element that satisfies the following predicate.
    ƒẊ++             Given [a,b], magically generate the infinite Fibonacci-like
                     sequence from [a,b] without [a,b] at the start.
 ö£⁰                 Is the input in that list (given that it is in sorted order)?
```
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 92 90 89 91 83 82 bytes
-3 bytes -1 byte thanks to ThePirateBay
-8 -9 bytes thanks to Neil.
```
f=(n,a=1,b=0,c=(a,b)=>b<n?c(a+b,a):b>n)=>c(a,b)?b+2<a?f(n,a-1,b+1):f(n,b-~a):[b,a]
```
[Try it online!](https://tio.run/##TU5PT4MwFD/Dp3g70YaytFVjHOs47eJBDx4JhxbphiGtKbjFuPnVsWVMbS@/v@@9N3mQfe3a9yEz9rUZRy2QIVIwogQltUCSKCw2am2KGslUEYlXamO8VE9WoVK@loUOpcyXUoZXgajs2ydLn6/Gg3QwNP3Qg4AyjkpGKGEV8Yj/QXbn4c0FUkpuCaMzYcR/PhP@P0UJv8b4vTcePKzyOJ6WLbV1W1nvUWAgNvAVR@ES1/QfnRcA9GSVtMJ5HNXW9LZrlp3doUSjBFKYXY8S7PNBenx5flr2g2vNrtWf6DILh36rYaahshDiUmcVnE7zzkB@DV7hcFE07J09gmmOsHXOOpQswkvCyHN8xvn4Aw "JavaScript (Node.js) – Try It Online")
Note: this solution relies on the fact that there are never multiple minimal solutions.
# Proof that there are never multiple solutions:
Let `FIB(a,b,k)` be the Fibonacci-like sequence starting with `a,b`:
```
FIB(a,b,0) = a
FIB(a,b,1) = b
FIB(a,b,k) = FIB(a,b,k-1) + FIB(a,b,k-2)
```
## Lemma 1
The difference between Fibonacci-like sequences is itself Fibonacci-like, i.e. `FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k)`.
The proof is left to reader.
## Lemma 2
For `n >= 5`, a solution `a,b` exists satisfying `a+b < n`:
if `n` is even, `FIB(0,n/2,3) = n`
if `n` is odd, `FIB(1,(n-1)/2,3) = n`
## Proof
Cases where `n < 5` can be checked exhaustively.
Suppose we have two minimal solutions for `n >= 5`, `a0,b0` and `a1,b1` with `a0 + b0 = a1 + b1` and `a0 != a1`.
Then there exist `k0,k1` such that `FIB(a0,b0,k0) = FIB(a1,b1,k1) = n`.
* Case 1: `k0 = k1`
WLOG assume `b0 < b1` (and therefore `a0 > a1`)
Let `DIFF(k)` be the difference between the Fibonnaci-like sequences starting with `a1,b1` and `a0,b0`:
`DIFF(k) = FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k)` (Lemma 1)
`DIFF(0) = a1 - a0 < 0`
`DIFF(1) = b1 - b0 > 0`
`DIFF(2) = (a1+b1) - (a0+b0) = 0`
`DIFF(3) = DIFF(1) + DIFF(2) = DIFF(1) > 0`
`DIFF(4) = DIFF(2) + DIFF(3) = DIFF(3) > 0`
Once a Fibonnaci-like sequence has 2 positive terms, all subsequent terms are positive.
Thus, the only time `DIFF(k) = 0` is when `k = 2`, so the only choice for `k0 = k1` is `2`.
Therefore `n = FIB(a0,b0,2) = a0 + b0 = a1 + b1`
The minimality of these solutions contradicts Lemma 2.
* Case 2: `k0 != k1`:
WLOG assume `k0 < k1`.
We have `FIB(a1,b1,k1) = n`
Let `a2 = FIB(a1,b1,k1-k0)`
Let `b2 = FIB(a1,b1,k1-k0+1)`
Then `FIB(a2,b2,k0) = FIB(a1,b1,k1) = FIB(a0,b0,k0)` (exercise for the reader)
Since `FIB(a1,b1,k)` is non-negative for `k >= 0`, it is also non-decreasing.
This gives us `a2 >= b1 > a0` and `b2 >= a1+b1 = a0+b0`.
Then let `DIFF(k) = FIB(a2,b2,k) - FIB(a0,b0,k) = FIB(a2-a0,b2-b0,k)` (Lemma 1)
`DIFF(0) = a2 - a0 > 0`
`DIFF(1) = b2 - b0 >= (a0 + b0) - b0 = a0 >= 0`
`DIFF(2) = DIFF(0) + DIFF(1) >= DIFF(0) > 0`
`DIFF(3) = DIFF(1) + DIFF(2) >= DIFF(2) > 0`
Once again, `DIFF` has 2 positive terms and therefore all subsequent terms are positive.
Thus, the only time when it's possible that `DIFF(k) = 0` is `k = 1`, so the only choice for `k0` is `1`.
`FIB(a0,b0,1) = n`
`b0 = n`
This contradicts Lemma 2.
[Answer]
# [Haskell](https://www.haskell.org/), ~~76 72~~ 74 bytes
EDIT:
* -4 bytes: @H.PWiz suggested using `/` instead of `div`, although this requires using a fractional number type.
* +2 bytes: Fixed a bug with `Enum` ranges by adding `-1`.
`f` takes a value of `Double` or `Rational` type and returns a tuple of same.
`Double` should suffice for all values that are not large enough to cause rounding errors, while `Rational` is theoretically unlimited.
```
f n|let a?b=b==n||b<n&&b?(a+b)=[(a,s-a)|s<-[1..],a<-[0..s/2-1],a?(s-a)]!!0
```
[Try it online!](https://tio.run/##RY7BisIwEIbvPsVYFpuQJiaFZUGMfYe9qoeJZmnZOJUmokLfvZuuBw/DfPP9DPwtxl8fwhTb/l6ChdbjGRTc@@Ec85714oId2Y6SH/CUPm4UOvJRXfDK2IHk7vVKQhQbKIRgB/aonhzkDkpWwgZe@QOEgLJ6i@csCl5w9gPEuUr9N6auJwxqyCW4@u8w5XAMPgE2zjpraRzdllYr1zAUjts9wypK5GPcyr1R6lhhBq1UXNfS5Kthc3xcLvU0GagNmE8wWufJqOuZNdRffw "Haskell – Try It Online") (with H.PWiz's header adjustments to input/output `Rational`s in integer format)
# How it works
* `?` is a locally nested operator in the scope of `f`. `a?b` recursively steps through the Fibonacci-like sequence starting with `a,b` until `b>=n`, returning `True` iff it hits `n` exactly.
* In the list comprehension:
	+ `s` iterates through all numbers from `1` upwards, representing the sum of `a` and `b`.
	+ `a` iterates through the numbers from `0` to `s/2-1`. (If `s` is odd the end of range rounds up.)
	+ `a?(s-a)` tests if the sequence starting with `a,s-a` hits `n`. If so, the list comprehension includes the tuple `(a,s-a)`. (That is, `b=s-a`, although it was too short to be worth naming.)
	+ `!!0` selects the first element (hit) in the comprehension.
[Answer]
# [APL (Dyalog)](https://www.dyalog.com/), ~~75~~ ~~71~~ ~~64~~ ~~59~~ ~~53~~ ~~48~~ ~~44~~ 43 bytes
*2 bytes saved thanks to @Adám*
*12 bytes saved thanks to @ngn*
```
⊃o/⍨k∊¨+\∘⌽⍣{k≤⊃⍺}¨o←a/⍨</¨a←,⍉|-\¨⍳2⍴1+k←⎕
```
[Try it online!](https://tio.run/##FYy9DsFgFIb39yrOVlLS79RfiRswuQFLE2GopFbBRKifTywSO8O3Y5FYeinnRup0e3@feD6rjxfxLJ0WcrkNhrK7GkCy/aSQ4yYNxLpEsmPu/JFkdzn/xD6WiRye2or9rnOX6iUud/0gd7GamtjDqj7KndhXKPbNfqKp0gvFFksVpbUfr@fJaTtRRKVcmmqNjQExKAQ1QE1QC9QGdUARqAs2YAaH4Aa4CW6B2@AOOAJ3EWprzB8)
Uses `⎕IO←0`.
**How?** *This had gone real nuts.*
`k←⎕` - assign input to `k`
`⍳2⍴1+k←⎕` - Cartesian product of the range `0` to `k` with itself
`|-\¨` - substract each right pair element from the left, and get absolute values
`a←,⍉` - transpose, flatten and assign to `a`
`o←a/⍨</¨a` - keep only pairs where the left element is smaller than the right, and assign to `o`
`o` now contains list of all pairs with `a < b`, ordered by their arithematical mean
`+\∘⌽⍣{k≤⊃⍺}¨o` - for each pair in `o`, apply fibonacci (reverse the pair and cumsum) until `k` or higher term is reached
`k∊¨` - then decide if `k` is this last term (meaning it is contained in the sequence)
`o/⍨` - and keep pairs in `o` where the previous check applies
`⊃` - return the first result.
[Answer]
# [Python 2](https://docs.python.org/2/), ~~127~~ ~~109~~ 107 bytes
*-2 bytes thanks to ovs (changing `and` to `*`)*
```
g=lambda x,a,b:a<=b<x and g(x,b,a+b)or b==x
f=lambda n,s=1,a=0:g(n,a,s-a)*(a,s-a)or f(n,s+(a==s),a%s+(a<s))
```
**[Try it online!](https://tio.run/##VY7NjsIwDITvfQpfVkrASEnYvVT1k1QcHGgLEpuiOqDy9CWh/ObizPgba07XuO@Dm6aOjvzvdwwjMvqSK/LVCBx20KkRPfLS634ATzQW7ZMNKGSRyZSdCiknK9YLNc8Et8mUpWIi0cg/@VuJ1lNsJG5ZGgGCurYIyqDVG4TafQr7dxfrLAr4eLU1Jq1@0ZoZNDlm0bqHdO9gZjPs7vDm607RppK5DMKFj@cGDgFe3cqEnoZDiA@iVXnq5LJIM8SnAURzeroB "Python 2 – Try It Online")**
Any bonus points for `n,a,s-a`?
### Explanation:
* The first line declares a recursive lambda, `g`, which verifies whether `a, b` expanded as a Fibonacci sequence will reach `x`. It also checks that `a <= b`, one of the criteria of the question. (This would allow cases where `a == b`, but in such a case `0, a` would have already been discovered and returned).
	+ The chained inequality `a<=b<x` performs two handy tasks at once: verifying `a <= b`, and that `b < x`.
	+ If `b < x` yields `True`, the function calls itself again with the next two numbers in the Fibonacci sequence: `b, a+b`. This means the function will keep working out new terms until...
	+ If `b < x` yields `False`, then we have reached the point where we need to check if `b==x`. If so, this will return `True`, signifying that the initial pair `a, b` will eventually reach `x`. Otherwise, if `b > x`, the pair is invalid.
* The second line declares another recursive lambda, `f`, which finds the solution for a given value `n`. It recursively tries new initial pairs, `a, b`, until `g(n, a, b)` yields `True`. This solution is then returned.
	+ The function recursively counts up initial Fibonacci pairs using two variables, `s` (initially 1) and `a` (initially 0). On each iteration, `a` is incremented, and `a, s-a` is used as the first pair. However, when `a` hits `s`, it is reset back to 0, and `s` is incremented. This means the pairs are counted up in the following pattern: 
	```
	
	s=1 (0, 1) (1, 0)
	s=2 (0, 2) (1, 1)  (2, 0)
	s=3 (0, 3) (1, 2), (2, 1), (3, 0)
	
	```
	 Obviously, this contains some invalid pairs, however these are eliminated instantly when passed to `g` (see first bullet point).
	+ When values `a` and `s` are found such that `g(n, a, s-a) == True`, then this value is returned. As the possible solutions are counted up in order of 'size' (sorted by mean, then min value), the first solution found will always be the smallest, as the challenge requests.
[Answer]
# [R](https://www.r-project.org/), ~~183 bytes~~ 160 bytes
```
n=scan();e=expand.grid(n:0,n:0);e=e[e[,2]>e[,1],];r=e[mapply(h<-function(n,a,b,r=a+b)switch(sign(n-r)+2,F,T,h(n,b,r)),n,e[,1],e[,2]),];r[which.min(rowSums(r)),]
```
[Try it online!](https://tio.run/##JYzBDoMgEAV/Z4mrQY@19NgfaG@EAyIVkrIa0Nh@PUV7eO8wmUzMmUQymoD1VtjPomlspuhHoAvHshNLK7FTt/KtQtXHQoJelvcX3LV@bWRWPxMQahwwCl0NLO1@NQ6SnwqvI6s6vOMTXZGKwhgS/mtnmR1RuTtvXBM8QZz3xxYSHKLKLec8/wA "R – Try It Online")
**Thanks to Giuseppe for golfing off 23 bytes**
Code explanation
```
n=scan()                        #STDIO input
e=expand.grid(n:0,n:0)          #full outer join of integer vector n to 0
e=e[e[,2]>e[,1],]               #filter so b > a
r=e[mapply(
  h<-function(n,a,b,r=a+b)switch(sign(n-r)+2,F,T,h(n,b,r)),
                                #create a named recursive function mid-call 
                                #(requires using <- vs = to denote local variable creation 
                                #rather than argument assignment
  n,e[,1],e[,2]),]              #map n, a and b to h() which returns a logical
                                #which is used to filter the possibilities
r[which.min(rowSums(r)),]       #calculate sum for each possibility, 
                                #get index of the minimum and return
                                #because each possibility has 2 values, the mean and 
                                #sum will sort identically.
```
[Answer]
# Mathematica, 117 bytes
```
If[#==1,{0,1},#&@@SortBy[(S=Select)[S[Range[0,s=#]~Tuples~2,Less@@#&],!FreeQ[LinearRecurrence[{1,1},#,s],s]&],Mean]]&
```
  
[Try it online!](https://tio.run/##HcyxCsIwFEbhV1ECReEObRenQHAQhArauF0yhPBXC22UJB2k2FePRTjjxxltemK0qXc2dxu5yeeOhZQVzSVVXxKFUvoV0vHDOy01Bri0Z82t9Q9wSVEKs9yn94C41NQgRqVEYWh7CsCNm97DhhZuCgHegefqf6Vo1lZ3gfXGFPkaep9Ux/XB5B8 "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 19 bytes
```
ṫ-Sṭµ¡³e
0rŒcÇÐfSÐṂ
```
[Try it online!](https://tio.run/##AS0A0v9qZWxsef//4bmrLVPhua3CtcKhwrNlCjByxZJjw4fDkGZTw5DhuYL///8xMDA "Jelly – Try It Online")
-1 byte thanks to [the proof](https://codegolf.stackexchange.com/a/147843/41024) by [cardboard\_box](https://codegolf.stackexchange.com/users/6683/cardboard-box). In case it's disproved, you can append `UṂṚ` to the end of the second line for 22 bytes in total.
[Answer]
## [GolfScript](https://tio.run/##S8/PSStOLsosKPn/v87KL1qn2lDbKlGnOlrPOjG2Vr9WPzYayK6r1vOzqa3Wc9CuLc/IzEmNsfazBcrGVmsa2sZY1@pUa8RY12nXqgApTeu6OnUF9Zj//43MAQ) - ~~88~~ 77 bytes
```
~:N[,{1+:a,{[.;a]}/}/][{[.~{.N<}{.@+}while\;N=]}/]{)1=\;},{(\;~+}$(\;);~~' '\
```
I did not check for multiple solutions, thanks to cardboard\_box!
### Explanation
```
~:N                           # Reads input
[,{1+:a,{[.;a]}/}/]           # Creates an array of pairs [a b]
[{[.~{.N<}{.@+}while\;N=]}/]  # Compute solutions
{)1=\;},         # Pairs that are not solutions are discarded
{(\;~+}$         # Sorts by mean
(\;);~~' '\      # Formats output
```
[Answer]
## Batch, ~~160~~ 158 bytes
```
@set/aa=b=0
:g
@if %a% geq %b% set/ab-=~a,a=0
@set/ac=a,d=b
:l
@if %c% lss %1 set/ad+=c,c=d-c&goto l
@if %c% gtr %1 set/aa+=1,b-=1&goto g
@echo %a% %b%
```
]