Problems

Filters
Clear Filters

3 problems found

2006 Paper 3 Q8
D: 1700.0 B: 1500.0
proof proof by induction polynomials differentiation product rule linearity operator abstract algebra

\(\triangle\) is an operation that takes polynomials in \(x\) to polynomials in \(x\); that is, given any polynomial \(\h(x)\), there is a polynomial called \(\triangle \h(x)\) which is obtained from \(\h(x)\) using the rules that define \(\triangle\). These rules are as follows:

  1. \(\triangle x = 1\,\);
  2. \(\triangle \big( \f(x)+\g(x)\big) = \triangle \f(x) + \triangle\g(x)\,\) for any polynomials \(\f(x)\) and \(\g(x)\);
  3. \(\triangle \big( \lambda \f(x)\big) =\lambda \triangle \f(x)\) for any constant \(\lambda\) and any polynomial \(\f(x)\);
  4. \(\triangle \big( \f(x)\g(x)\big) = \f(x) \triangle \g(x) +\g(x)\triangle \f(x)\) for any polynomials \(\f(x)\) and \(\g(x)\).
Using these rules show that, if \(\f(x)\) is a polynomial of degree zero (that is, a constant), then \(\triangle \f(x) =0\). Calculate \(\triangle x^2\) and \(\triangle x^3\). Prove that \(\triangle \h(x) \equiv \dfrac{\d \h(x)}{\d x \ \ \ }\) for any polynomial \(\h(x)\). You should make it clear whenever you use one of the above rules in your proof. \(\vphantom{\int}\)

Solution: Claim: If \(f\) is a constant, then \(\triangle f = 0\) Proof: First consider \(f(x) = 1, g(x) = x\) then we must have: \begin{align*} && \triangle (1x) &= 1 \triangle x + x \triangle 1 \tag{iv} \\ &&&= 1 \cdot 1 + x \triangle 1 \tag{i} \\ \Rightarrow && 1 &= 1 + x \triangle 1 \tag{i} \\ \Rightarrow && \triangle 1 &= 0 \\ \Rightarrow && \triangle c &= 0 \tag{iii} \end{align*} \begin{align*} && \triangle (x^2) &= x \triangle x + x \triangle x \tag{iv} \\ &&&= x \cdot 1 + x \cdot 1 \tag{i} \\ &&&= 2x \\ \\ && \triangle (x^3) &= x^2 \triangle x + x \triangle (x^2) \tag{iv} \\ &&&= x^2 \cdot 1 + x \cdot 2x \tag{\(\triangle x^2 = 2x\)}\\ &&&= 3x^2 \end{align*} Claim: \(\triangle h(x) = \frac{\d h(x)}{\d x}\) for any polynomial \(h\) Proof: Since both \(\triangle\) and \(\frac{\d}{\d x}\) are linear (properties \((ii)\) and \((iii)\)) it suffices to prove that: \(\triangle x^n = nx^{n-1}\). For this we proceed by induction. Base cases (we've proved up to \(n = 3\) so we're good). Suppose it's true for some \(n\), then consider \(n + 1\), \begin{align*} && \triangle (x^{n+1}) &= x \triangle (x^n) + x^n \triangle x \tag{iv} \\ &&&= x \cdot n x^{n-1} + x^n \triangle x \tag{Ind. hyp.} \\ &&&= nx^n + x^n \tag{i} \\ &&&= (n+1)x^{n} \end{align*} Therefore it's true for for \(n+1\). Therefore by induction it's true for all \(n\).

View
1992 Paper 2 Q4
D: 1600.0 B: 1500.0
differentiation from first principles polynomials product rule proof by induction linearity abstract algebra operator

\(\lozenge\) is an operation which take polynomials in \(x\) to polynomials in \(x\); that is, given a polynomial \(\mathrm{h}(x)\) there is another polynomial called \(\lozenge\mathrm{h}(x)\). It is given that, if \(\mathrm{f}(x)\) and \(\mathrm{g}(x)\) are any two polynomials in \(x\), the following are always true:

  1. \(\lozenge(\mathrm{f}(x)\mathrm{g}(x))=\mathrm{g}(x)\lozenge\mathrm{f}(x)+\mathrm{f}(x)\lozenge\mathrm{g}(x),\)
  2. \(\lozenge(\mathrm{f}(x)+\mathrm{g}(x))=\lozenge\mathrm{f}(x)+\lozenge\mathrm{g}(x),\)
  3. \(\lozenge x=1\)
  4. if \(\lambda\) is a constant then \(\lozenge(\lambda\mathrm{f}(x))=\lambda\lozenge\mathrm{f}(x).\)
Show that, if \(\mathrm{f}(x)\) is a constant (i.e., a polynomial of degree zero), then \(\lozenge\mathrm{f}(x)=0.\) Calculate \(\lozenge x^{2}\) and \(\lozenge x^{3}.\) Prove that \(\lozenge\mathrm{h}(x)=\dfrac{\mathrm{d}}{\mathrm{d}x}(\mathrm{h}(x))\) for any polynomial \(\mathrm{h}(x)\).

Solution: Claim: If \(f(x) = c\) then \(\lozenge f(x) = 0\) Proof: Consider \(g(x) = x\) then \begin{align*} (1) && \lozenge(f(x)g(x)) &= g(x) \lozenge f(x) + f(x) \lozenge g(x) \\ \Rightarrow && \lozenge(c x) &= x \lozenge f(x) + c \lozenge x \\ (4) && \lozenge(c x) &= c \lozenge x \\ \Rightarrow && 0 &= x \lozenge f(x) \\ \Rightarrow && \lozenge f(x) &= 0 \end{align*} \begin{align*} (1) && \lozenge(x^2) &= x \lozenge x + x \lozenge x \\ (3) &&&= 2 x \cdot 1 \\ &&&= 2x \\ \\ (1) && \lozenge (x^3) &= x^2 \lozenge x + x \lozenge (x^2) \\ &&&= x^2 \cdot \underbrace{1}_{(3)} + x \cdot\underbrace{ 2x}_{\text{previous part}} \\ &&&= 3x^2 \end{align*} Claim: \(\lozenge h(x) = \frac{\d }{\d x} ( h(x))\) for any polynomial \(h\). Proof: (By (strong) induction on the degree of \(h\)). Base case: True, we proved this in the first part of the question. Inductive step: Assume true for all polynomials of degree less than or equal to \(k\). Then consider \(n = k+1\). We can write \(h(x) = ax^{k+1} + h_k(x)\) where \(h_k(x)\) is a polynomial of degree less than or equal to \(k\). Then notice: \begin{align*} && \lozenge (h(x)) &= \lozenge (ax^{k+1} + h_k(x)) \\ (2) &&&= \lozenge (ax^{k+1})+ \lozenge (h_k(x)) \\ &&&=\underbrace{a\lozenge (x^{k+1})}_{(4)}+ \underbrace{\frac{\d}{\d x} (h_k(x))}_{\text{inductive hypothesis}}\\ &&&= a \underbrace{\left (x \lozenge x^k + x^k \lozenge x \right)}_{(1)} + \frac{\d}{\d x} (h_k(x)) \\ &&&= a \left ( x \cdot \underbrace{k x^{k-1}}_{\text{inductive hyp.}} + x^k \cdot \underbrace{1}_{(3)} \right) + \frac{\d}{\d x} (h_k(x)) \\ &&&= (k+1)a x^k + \frac{\d}{\d x} (h_k(x)) \\ &&&= \frac{\d }{\d x} \left ( ax^{k+1} + h_k(x) \right) \\ &&&= \frac{\d }{\d x} (h(x)) \end{align*} Therefore since our statement is true for \(n=0\) and if it is true for \(n=k\) it is true for \(n=k+1\) by the principle of mathematical induction it is true for all \(n \geq 0\)

View
1987 Paper 2 Q10
D: 1500.0 B: 1500.0
groups group axioms binary operation closure associativity identity element inverse proof abstract algebra

The set \(S\) consists of \(N(>2)\) elements \(a_{1},a_{2},\ldots,a_{N}.\) \(S\) is acted upon by a binary operation \(\circ,\) defined by \[ a_{j}\circ a_{k}=a_{m}, \] where \(m\) is equal to the greater of \(j\) and \(k\). Determine, giving reasons, which of the four group axioms hold for \(S\) under \(\circ,\) and which do not. Determine also, giving reasons, which of the group axioms hold for \(S\) under \(*\), where \(*\) is defined by \[ a_{j}*a_{k}=a_{n}, \] where \(n=\left|j-k\right|+1\).

Solution:

  1. (Closure) This operation is clearly closed by construction
  2. (Associative) \(a_j \circ (a_k \circ a_l) = a_j \circ a_{\max(k,l)} = a_{\max(j,k,l)} = a_{\max(j,k)} \circ a_l = (a_j \circ a_k) \circ a_l\), so it is associative
  3. (Identity) \(a_1 \circ a_k = a_{\max(1,k)} = a_k = a_{\max(k,1)} = a_k \circ a_1\) so \(a_1\) is an identity.
  4. (Inverses) There is no inverse, since \(a_N \circ a_k = a_N\) for all \(k\), and hence \(a_N\) can have no inverse.
  1. (Closure) \(n = |j-k|+1 \geq 1\) so we need to show that \(n \leq N\) to ensure closure. This is true since the largest \(j-k\) can be is if \(j = N\) and \(k = 1\), and this also satisfies \(|j-k| + 1 \leq N\). Hence the operation is closed.
  2. (Associative) \(a_j * (a_k * a_l) = a_j * (a_{|k-l|+1}) = a_{|j-|k-l|-1|+1}\). \((a_j * a_k) * a_l = a_{|j-k|+1}*a_l = a_{|l-|j-k|-1|+1}\). \(a_2 * (a_2 * a_3) = a_2 * a_2 = a_1\). \((a_2 *a_2)*a_3 = a_1 * a_3 = a_3 \neq a_2\) therefore this isn't associative for any \(N > 2\)
  3. (Identity) \(a_1\) is an identity, since \(a_1 * a_k = a_{|k-1|+1} = a_{k-1+1} = a_k\).
  4. (Inverse) Every element is self-inverse since \(a_k * a_k = a_{|k-k|+1} = a_1\)

View