Induction Proof Clarification

60 Views Asked by At

Problem

$T= \{3^0, \ldots, 3^{k-1}\}, t>0$. We know that $T \in P(T)$ and for any $A \in P(T), A \subseteq T$ and further for any $B \in P(A) \subset P(T)$ which implies $B \subset T$.

So if we consider $A=T$ and $B=T$, we will get the maximum of $S$.

So the maximum is $$\sum_{a \in T}a + \sum_{b \in T}b =2\left(\sum_{k=0}^{t-1} 3^k \right) = \left(\sum_{k=0}^{t-1} 2\cdot 3^k \right)$$

I think that I solved part a) of this problem correctly, it seems straightforward by logic, but I don't know how to prove it.

1

There are 1 best solutions below

0
On

All the elements of $T$ are positive, hence we should include all of them.

Note that you can further simplify $$2\sum_{k=0}^{t-1} 3^k =2\cdot \frac{3^t-1}{2}=3^t-1$$

We have illustrated that we can attain this number. Furthermore, we can't attain a larger number than $3^t-1$ since we have used up all the positive numbers that we can sum. Hence, this is the maximum value that we can attain.


If you insist to write an induction:

I will leave the base case to you.

Suppose $T_k = \{ 3^i: i \in \{1, \ldots, k-1\}\}$ and we define $S_k$ accordingly and we have $\max (S_k)=3^k-1$.

Now consider the set $T_{k+1}$ and we defined $S_{k+1}$ accordingly.

Note that we have $T_{k+1}=T_k \cup \{3^k\}$ and consider the $A_{k+1}$ and $B_{k+1}$ that corresponds that attains $\max(S_{k+1})$. Suppose $3^k \notin A_{k+1}$ or $3^{k} \notin B_{k+1}$, then we have

$$\sum_{a \in A_{k+1}\cup \{3^k\}} a + \sum_{b \in A_{k+1}\cup \{3^k\}} b \ge \max(S_{k+1}) + 3^k > \max(S_{k+1})$$ which is a contradiction. Hence we must have $3^k \in A_{k+1}$ and $3^k \in B_{k+1}$.

We have

$$\sum_{a \in A_{k+1}} a + \sum_{b \in B_{k+1}} b= \max(S_{k+1})$$

$$\sum_{a \in A_{k+1}\setminus \{3^k\}} a + \sum_{b \in B_{k+1} \setminus \{3^k\}} b= \max(S_{k+1})-2\cdot 3^k$$

Since $A_{k+1}\setminus \{3^k\}$ and $B_{k+1}\setminus \{3^k\}$ are subsets of $T_k$,

We have $$\max(S_{k+1})-2\cdot 3^k \le \max(S_k)=3^k-1$$

$$\max(S_{k+1}) \le 3^{k+1}-1$$

Hence $3^{k+1}-1$ is an upperbound and we just have to illustrate that we can attain it, i.e. by summing up every element.