For a fixed positive integer n consider the equation

Nov 2016
24
0
Slovenia
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:
May 2016
1,310
551
USA
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.
 
  • Like
Reactions: 1 person
Nov 2016
24
0
Slovenia
In the first condition there is,

1. for each k=1,…,n−1 either x_k>0 or x_(k+1)=0
 
Last edited:
May 2016
1,310
551
USA
In the first condition there is,

1. for each k=1,…,n−1 either x_k>0 or x_(k+1)=0
OK

I see. I badly misread the original problem. I apologize.

$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.}$
 
Nov 2016
24
0
Slovenia
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
 
May 2016
1,310
551
USA
It does make a difference. I meant to use $\ge 1$ not $> 1.$

$x_1 = 1\ and\ x_i = 0\ for\ i\ such\ that\ 1 < i \le n.$

$\displaystyle 1 * n + \sum_{i=2}^n(i * 0) = n + 0 = n.$

$\text{And clearly }1 = x_1 \implies x_1 > 0.$

$\text{And just as clearly,}$

$x_i = 0\ for\ i\ such\ that\ 1 < i \le n \implies x_{k+1} = 0\ for\ k\ such\ that\ 1 \le k < n.$
 
May 2016
1,310
551
USA
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:
  • Like
Reactions: 1 person
Nov 2016
24
0
Slovenia
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