Managed to do this challenge. The way the code works is to make a table of equations describing the FSM to match the numbers, and then algebraically reduces it down to a single term. The regexes it produces are longer than they need to be but they work. Simple solution but took a lot of thinking to get there.
Here it is in action for n = 5:
0 = 0(0) | 2(1)
1 = 0(1) | 3(0)
2 = 1(0) | 3(1)
3 = 1(1) | 4(0)
4 = 2(0) | 4(1)
0 = 0(0) | 2(1)
1 = 0(1) | 3(0)
2 = 1(0) | 3(1)
3 = 1(1) | 4(1*0)
4 = 2(0)
0 = 0(0) | 2(1)
1 = 0(1) | 3(0)
2 = 1(0) | 3(1)
3 = 1(1) | 2(01*0)
0 = 0(0) | 2(1)
1 = 0(1) | 3(0)
2 = 1(0) | 3(1)
3 = 1(1) | 2(01*0)
0 = 0(0) | 2(1)
1 = 0(1) | 1(10) | 2(01*00)
2 = 1((0|11)) | 2(01*01)
0 = 0(0) | 2((01*01)*1)
1 = 0(1) | 2((01*01)*01*00)
2 = 1((10)*(0|11))
0 = 0(0) | 1((10)*(0|11)(01*01)*1)
1 = 0(1) | 1((10)*(0|11)(01*01)*01*00)
0 = 0(0) | 1(((10)*(0|11)(01*01)*01*00)*(10)*(0|11)(01*01)*1)
1 = 0(1)
0 = 0((0|1((10)*(0|11)(01*01)*01*00)*(10)*(0|11)(01*01)*1))
regex: ^(0|1((10)*(0|11)(01*01)*01*00)*(10)*(0|11)(01*01)*1)+$