I was solving an interview problem, which goes like this, “A man can jump either 1 step or 2 step in a go, find the total number of unique ways in which he can reach to the nth step, if he initially was on the 0th step. Unique means that, for say n = 5 : 2 -> 1 -> 2, 2 -> 2 -> 1 and 1 -> 2 -> 2 are considered same.”
This is similar to the the popular programming puzzle with the constraint of counting only ‘unique’ ways added to it, where you are allowed to count redundant ways(which is similar to the Fibonacci sequence, following the recurrence relation dp[n] = dp[n-1] + dp[n-2]). But because this recurrence relation also counts redundant ways, this won’t work in the current version of the problem. After thinking for about 5-10 mins, I realised that it is just the modified version of the Coin Change problem with just 2 coins(of denomination 1 and 2). Needless to say I got AC but this left me thinking how does Coin Change avoid repetition but Fibonacci does not(okay, it is not exactly the Fibonacci sequence, but I am calling it because of the similarity in recurrence relation.). I get the intuition but can anyone present a more formal Mathematical proof?