# For a fixed positive integer n consider the equation

#### TobiWan

For a fixed positive integer n consider the equation

x1+2x_2+â‹¯+nx_n=n

in which x_1,â€¦,x_n can take nonnegative integer values. Show that there are as many solutions (x_1,â€¦,x_n) satisfying

1. for each k=1,â€¦,nâˆ’1 either x_k>0 or x_k+1=0,
as there are solutions (x_1,â€¦,x_n) satisfying

2. for each k=1,â€¦,n either x_k=0 or x_k=1

Last edited:

#### JeffM1

I like to start thinking about such problems as follows:

$1 \le k \le n \implies x_k \in \mathbb N^+.$

If n = 2 (You did not specify that n > 1, but that seems to be required)

$\displaystyle \sum_{k=1}^nkx_k = n \implies 1 * x_1 + 2 * x_2 = 2 \implies x_1 = 0\ and\ x_2 = 1.$

$x_1 \not > 0\ and\ x_2 \ne 0.$

So no solutions.

$x_1 = 0\ and\ x_2 = 1$.

So one solution.

So if I understand the problem, which I may well not, the proposition is false and cannot be proved.

1 person

#### TobiWan

In the first condition there is,

1. for each k=1,â€¦,nâˆ’1 either x_k>0 or x_(k+1)=0

Last edited:

#### JeffM1

In the first condition there is,

1. for each k=1,â€¦,nâˆ’1 either x_k>0 or x_(k+1)=0
OK

$Given:\ k,\ n \in \mathbb Z,\ n > 1,\ 1 \le k \le n,$

$x_k \in \mathbb Z,\ x_k \ge 0,\ and\ \displaystyle \sum_{i=1}^n ix_i = n.$

$Prove:\ \text{The number of solutions such that }k < n \implies either\ x_k > 1\ or\ x_{k+1} = 0$

$\text{equals the number of solutions such that }k \le n \implies either\ x_k = 0\ or\ x_k = 1.$

Do I have the problem correctly?

I still like to look at a few specific cases because that frequently gives a clue on how to solve the general problem. Let's start with n = 2.

$x_k \not > 2.$

$\therefore x_k = 0,\ 1,\ or\ 2.$

$\text{(0, 0), (0, 2), (1, 0), (1, 1), (1, 2), (2, 1), (2, 2) are not solutions.}$

$\text{(0, 1) and (2, 0) are solutions.}$

The first condition but not the second applies to the second solution so that number is 1.

The second condition but not the first applies to the first solution so that number is also 1. The numbers are equal.

I would now try at least n = 3 and maybe even n = 4 and n = 5. I suspect that exploration has a high probability of showing a path to a general proof. For example, it is now fairly obvious that

$\text{(0, ... 1) is always a solution that satisfies the second condition and}$

$\text{(n, 0 ...) is always a solution that satisfies the first condition.}$

#### TobiWan

OK

$Prove:\ \text{The number of solutions such that }k < n \implies either\ x_k > 1\ or\ x_{k+1} = 0$

Do I have the problem correctly?
There should have been x_k>0, not 1, but it probably doesn't make a diffrence

#### TobiWan

Does it really end the proof?

#### JeffM1

No, not at all. What I was saying is that by exploring cases with small n, you will learn about the problem. It is an excellent though not foolproof way to FIND a proof.

Notice that choosing n = 2, there were 9 possible cases. ONLY TWO were solutions. One condition applied to one solution and the other condition applied to the other solution. And it was fairly easy to show that analogous solutions exist for n > 2.

Try n = 3 and n = 4 with 16 and 25 cases. If again there are still only two solutions, that is encouraging. That would suggest trying to prove that those are the only two solutions for any n.

Last edited by a moderator:
1 person

#### TobiWan

but for n=3 it's a false, because only (0,1) applies to the second condition. To the first condition applies (2,0), (3,0), (4,0) and so on