My Math Forum For a fixed positive integer n consider the equation

 Algebra Pre-Algebra and Basic Algebra Math Forum

 November 18th, 2016, 08:30 AM #1 Newbie   Joined: Nov 2016 From: Slovenia Posts: 24 Thanks: 0 For a fixed positive integer n consider the equation 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 by TobiWan; November 18th, 2016 at 08:36 AM.
 November 18th, 2016, 09:21 AM #2 Senior Member   Joined: May 2016 From: USA Posts: 1,310 Thanks: 551 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. Thanks from topsquark
 November 19th, 2016, 03:25 AM #3 Newbie   Joined: Nov 2016 From: Slovenia Posts: 24 Thanks: 0 In the first condition there is, 1. for each k=1,…,n−1 either x_k>0 or x_(k+1)=0 Last edited by TobiWan; November 19th, 2016 at 03:35 AM.
November 19th, 2016, 06:32 AM   #4
Senior Member

Joined: May 2016
From: USA

Posts: 1,310
Thanks: 551

Quote:
 Originally Posted by TobiWan 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.}$

November 20th, 2016, 08:45 AM   #5
Newbie

Joined: Nov 2016
From: Slovenia

Posts: 24
Thanks: 0

Quote:
 Originally Posted by JeffM1 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

November 20th, 2016, 08:46 AM   #6
Newbie

Joined: Nov 2016
From: Slovenia

Posts: 24
Thanks: 0

Quote:
 Originally Posted by JeffM1 (n, 0 ...) is always a solution that satisfies the first condition.}$why?  November 20th, 2016, 10:31 AM #7 Senior Member Joined: May 2016 From: USA Posts: 1,310 Thanks: 551 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.\$
 November 20th, 2016, 11:43 AM #8 Newbie   Joined: Nov 2016 From: Slovenia Posts: 24 Thanks: 0 Does it really end the proof?
 November 20th, 2016, 01:41 PM #9 Senior Member   Joined: May 2016 From: USA Posts: 1,310 Thanks: 551 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. Thanks from topsquark Last edited by skipjack; November 25th, 2016 at 07:39 AM.
 November 23rd, 2016, 07:45 AM #10 Newbie   Joined: Nov 2016 From: Slovenia Posts: 24 Thanks: 0 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

 Tags equation, fixed, integer, positive

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post John Travolski Algebra 6 March 16th, 2016 05:23 PM mandradebs Number Theory 2 October 19th, 2014 07:43 AM Alann Number Theory 7 November 7th, 2012 08:39 AM K Sengupta Math Events 4 July 1st, 2012 02:03 AM ducnhuandoan Number Theory 4 May 1st, 2012 04:46 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top