the problem is:for n>=1,let an be the number of ways to write n as an ordered sum
of positive integers where each summand is at least 2.(For example, a5=3
because here we may represent 5 by 5,by 2+3, and by 3+2) Find and solve a
recurrence relation for an.
can someone kindly teach me how to solve this?i have been thinking on it for many hours...thanx
>The answer appears to be
>1 (if N<3)
>1 plus N-3 (if N>2) I'm sorry, that was careless of me. It's the answer for expressing N as one integer or the sum of two positive integers, whereas the original question obviously meant an ordered sum of any length. (though the examples given were only of two, which offers me some excuse).
To attack the problem, first change the restriction that each summand must be at least 2 to at least 1 (so that, e.g., 4 can be 1 plus 1 plus 1 plus 1). (Nonetheless 0 can still be written as '0', so the number of ways of writing 0 is 1.)
Let F(N) be the function that gives the answer for N.
The number n can be written in the following ways
N itself followed by the number of ways of writing zero
N-1 followed by the number of ways of writing 1
N-2 followed by the number of ways of writing 2
....
1 followes by the number of ways of writing N-1.
F(N) therefore equals F(0) plus F(1) plus F(2)...F(N-1).
But we need A(N) in which the summand 1 is disallowed. This can be achieved simply by taking the expression for F(N) and knocking out F(1) and F(N-1).
What remains is therefore
A(0)=1
A(N) = A(0) plus sum for i=2 to N-2 of A(I).
checking
A(0) = 1
A(1) = 1
A(2) = 1
A(3) = 1
A(4) = 2
A(5) = 3
A(6) = 5
A(7) = 8
...