My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Thanks Tree2Thanks
Reply
 
LinkBack Thread Tools Display Modes
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.
TobiWan is offline  
 
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
JeffM1 is offline  
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.
TobiWan is offline  
November 19th, 2016, 06:32 AM   #4
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,310
Thanks: 551

Quote:
Originally Posted by TobiWan View Post
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.}$
JeffM1 is offline  
November 20th, 2016, 08:45 AM   #5
Newbie
 
Joined: Nov 2016
From: Slovenia

Posts: 24
Thanks: 0

Quote:
Originally Posted by JeffM1 View Post
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 is offline  
November 20th, 2016, 08:46 AM   #6
Newbie
 
Joined: Nov 2016
From: Slovenia

Posts: 24
Thanks: 0

Quote:
Originally Posted by JeffM1 View Post
(n, 0 ...) is always a solution that satisfies the first condition.}$
why?
TobiWan is offline  
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.$
JeffM1 is offline  
November 20th, 2016, 11:43 AM   #8
Newbie
 
Joined: Nov 2016
From: Slovenia

Posts: 24
Thanks: 0

Does it really end the proof?
TobiWan is offline  
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.
JeffM1 is offline  
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
TobiWan is offline  
Reply

  My Math Forum > High School Math Forum > Algebra

Tags
equation, fixed, integer, positive



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Find the Smallest Positive Integer that... John Travolski Algebra 6 March 16th, 2016 05:23 PM
Bounded positive integer solutions of equation mandradebs Number Theory 2 October 19th, 2014 07:43 AM
Smallest positive integer... Alann Number Theory 7 November 7th, 2012 08:39 AM
Positive integer, perfect square and divisibility K Sengupta Math Events 4 July 1st, 2012 02:03 AM
Find all positive integer solutions of equation systems: ducnhuandoan Number Theory 4 May 1st, 2012 04:46 AM





Copyright © 2019 My Math Forum. All rights reserved.