text:
## Model selection¶

In a given regression situation, there are often many choices to be made. Recall our usual setup $$Y_{n \times 1} = X_{n \times p} \beta_{p \times 1} + \epsilon_{n \times 1}.$$

Any subset $A \subset \{1, \dots, p\}$ yields a new regression model $${\cal M}(A): Y_{n \times 1} = X[,A] \beta[A] + \epsilon_{n \times 1}$$ by setting $\beta[A^c]=0$.

Model selection is, roughly speaking, how to choose $A$ among the $2^p$ possible choices.

### Election data¶

Here is a dataset from the book that we will use to explore different model selection approaches.

Variable Description
$V$ votes for a presidential candidate
$I$ are they incumbent?
$D$ Democrat or Republican incumbent?
$W$ wartime election?
$G$ GDP growth rate in election year
$P$ (absolute) GDP deflator growth rate
$N$ number of quarters in which GDP growth rate $> 3.2\%$
In [1]:
%%R
url = 'http://stats191.stanford.edu/data/election.table'
pairs(election.table[,2:ncol(election.table)], cex.labels=3, pch=23,
bg='orange', cex=2)

## Problem & Goals¶

• When we have many predictors (with many possible interactions), it can be difficult to find a good model.
• Which main effects do we include?
• Which interactions do we include?
• Model selection procedures try to simplify / automate this task.
• Election data has $2^6=64$ different models with just main effects!

• This is generally an "unsolved" problem in statistics: there are no magic procedures to get you the "best model."

• In some sense, model selection is "data mining."

• Data miners / machine learners often work with very many predictors.

• Our model selection problem is generally at a much smaller scale than "data mining" problems.

• Still, it is a hard problem.

• Inference after selection is full of pitfalls!

## Hypothetical example¶

• Suppose we fit a a model $F: \quad Y_{n \times 1} = X_{n \times p} \beta_{p \times 1} + \varepsilon_{n \times 1}$ with predictors ${ X}_1, \dots, { X}_p$.
• In reality, some of the $\beta$’s may be zero. Let’s suppose that $\beta_{j+1}= \dots= \beta_{p}=0$.
• Then, any model that includes $\beta_0, \dots, \beta_j$ is correct: which model gives the best estimates of $\beta_0, \dots, \beta_j$?
• Principle of parsimony (i.e. Occam’s razor) says that the model with only ${X}_1, \dots, {X}_j$ is "best".

## Justifying parsimony¶

• For simplicity, let’s assume that $j=1$ so there is only one coefficient to estimate.
• Then, because each model gives an unbiased estimate of $\beta_1$ we can compare models based on $\text{Var}(\widehat{\beta}_1).$
• The best model, in terms of this variance, is the one containing only ${ X}_1$.
• What if we didn’t know that only $\beta_1$ was non-zero (which we don’t know in general)?
• In this situation, we must choose a set of variables.

## Model selection: choosing a subset of variables¶

• To "implement" a model selection procedure, we first need a criterion or benchmark to compare two models.
• Given a criterion, we also need a search strategy.
• With a limited number of predictors, it is possible to search all possible models (leaps in R).

### Candidate criteria¶

Possible criteria:

• $R^2$: not a good criterion. Always increase with model size $\implies$ "optimum" is to take the biggest model.
• Adjusted $R^2$: better. It "penalized" bigger models. Follows principle of parsimony / Occam’s razor.
• Mallow’s $C_p$ – attempts to estimate a model’s predictive power, i.e. the power to predict a new observation.

### Best subsets, $R^2$¶

Leaps takes a design matrix as argument: throw away the intercept column or leaps will complain.

In [2]:
%%R
election.lm = lm(V ~ I + D + W +G:I + P + N, election.table)
election.lm

Call:
lm(formula = V ~ I + D + W + G:I + P + N, data = election.table)

Coefficients:
(Intercept)            I            D            W            P            N
0.5111627   -0.0201077    0.0546159    0.0133905   -0.0007224   -0.0051822
I:G
0.0096901

In [3]:
%%R
X = model.matrix(election.lm)[,-1]
library(leaps)
election.leaps = leaps(X, election.table$V, nbest=3, method='r2') best.model.r2 = election.leaps$which[which((election.leaps$r2 == max(election.leaps$r2))),]
best.model.r2

   1    2    3    4    5    6
TRUE TRUE TRUE TRUE TRUE TRUE

Let's plot the $R^2$ as a function of the model size. We see that the full model does include all variables.

In [4]:
%%R
plot(election.leaps$size, election.leaps$r2, pch=23, bg='orange', cex=2)

## Best subsets, adjusted $R^2$¶

• As we add more and more variables to the model – even random ones, $R^2$ will increase to 1.

• Adjusted $R^2$ tries to take this into account by replacing sums of squares by mean squares $$R^2_a = 1 - \frac{SSE/(n-p-1)}{SST/(n-1)} = 1 - \frac{MSE}{MST}.$$

In [5]:
%%R
election.leaps = leaps(X, election.table$V, nbest=3, method='adjr2') plot(election.leaps$size, election.leaps$adjr2, pch=23, bg='orange', cex=2) best.model.adjr2 = election.leaps$which[which((election.leaps$adjr2 == max(election.leaps$adjr2))),]

    1     2     3     4     5     6
TRUE  TRUE FALSE FALSE  TRUE  TRUE

### Mallow’s $C_p$¶

• $C_p({\cal M}) = \frac{SSE({\cal M})}{\widehat{\sigma}^2} + 2 \cdot p({\cal M}) - n.$
• $\widehat{\sigma}^2=SSE(F)/df_F$ is the "best" estimate of $\sigma^2$ we have (use the fullest model), i.e. in the election data it uses all 6 main effects.
• $SSE({\cal M})$ is the $SSE$ of the model ${\cal M}$.
• $p({\cal M})$ is the number of predictors in ${\cal M}$.
• This is an estimate of the expected mean-squared error of $\widehat{Y}({\cal M})$, it takes bias and variance into account.
In [6]:
%%R
election.leaps = leaps(X, election.table$V, nbest=3, method='Cp') plot(election.leaps$size, election.leaps$Cp, pch=23, bg='orange', cex=2) best.model.Cp = election.leaps$which[which((election.leaps$Cp == min(election.leaps$Cp))),]
best.model.Cp

    1     2     3     4     5     6
FALSE  TRUE FALSE FALSE  TRUE  TRUE

## Search strategies¶

• Given a criterion, we now have to decide how we are going to search through the possible models.

• "Best subset": search all possible models and take the one with highest $R^2_a$ or lowest $C_p$ leaps. Such searches are typically feasible only up to $p=30$ or $40$.

• Stepwise (forward, backward or both): useful when the number of predictors is large. Choose an initial model and be "greedy".

• "Greedy" means always take the biggest jump (up or down) in your selected criterion.

### Implementations in R¶

• "Best subset": use the function leaps. Works only for multiple linear regression models.
• Stepwise: use the function step. Works for any model with Akaike Information Criterion (AIC). In multiple linear regression, AIC is (almost) a linear function of $C_p$.

### Akaike / Bayes Information Criterion¶

• Akaike (AIC) defined as $$AIC({\cal M}) = - 2 \log L({\cal M}) + 2 \cdot p({\cal M})$$ where $L({\cal M})$ is the maximized likelihood of the model.
• Bayes (BIC) defined as $$BIC({\cal M}) = - 2 \log L({\cal M}) + \log n \cdot p({\cal M})$$
• Strategy can be used for whenever we have a likelihood, so this generalizes to many statistical models.

### AIC for regression¶

• In linear regression with unknown $\sigma^2$ $$-2 \log L({\cal M}) = n \log(2\pi \widehat{\sigma}^2_{MLE}) + n$$ where $\widehat{\sigma}^2_{MLE} = \frac{1}{n} SSE(\widehat{\beta})$
• In linear regression with known $\sigma^2$ $$-2 \log L({\cal M}) = n \log(2\pi \sigma^2) + \frac{1}{\sigma^2} SSE(\widehat{\beta})$$ so AIC is very much like Mallow’s $C_p$.
In [7]:
%%R
n = nrow(X)
p = 7 + 1
c(n * log(2*pi*sum(resid(election.lm)^2)/n) + n + 2*p, AIC(election.lm))

[1] -66.94026 -66.94026

### Properties of AIC / BIC¶

• BIC will always choose a model as small or smaller than AIC (if using the same search direction).

• As our sample size grows, under some assumptions, it can be shown that

• AIC will (asymptotically) always choose a model that contains the true model, i.e. it won’t leave any variables out.
• BIC will (asymptotically) choose exactly the right model.

### Election example¶

Let's take a look at step in action. Probably the simplest strategy is forward stepwise which tries to add one variable at a time, as long as it can find a resulting model whose AIC is better than its current position.

When it can make no further additions, it terminates.

In [8]:
%%R
election.step.forward = step(lm(V ~ 1, election.table),
list(upper = ~ I + D + W + G:I + P + N),
direction='forward')
summary(election.step.forward)

Start:  AIC=-107.78
V ~ 1

Df Sum of Sq      RSS     AIC
+ D     1 0.0280805 0.084616 -111.80
+ I     1 0.0135288 0.099167 -108.47
+ P     1 0.0124463 0.100250 -108.24
<none>              0.112696 -107.78
+ N     1 0.0024246 0.110271 -106.24
+ W     1 0.0009518 0.111744 -105.96

Step:  AIC=-111.8
V ~ D

Df Sum of Sq      RSS     AIC
+ P     1 0.0099223 0.074693 -112.42
<none>              0.084616 -111.80
+ W     1 0.0068141 0.077801 -111.56
+ I     1 0.0012874 0.083328 -110.12
+ N     1 0.0000033 0.084612 -109.80

Step:  AIC=-112.42
V ~ D + P

Df  Sum of Sq      RSS     AIC
<none>               0.074693 -112.42
+ W     1 0.00031940 0.074374 -110.51
+ N     1 0.00018496 0.074508 -110.47
+ I     1 0.00002633 0.074667 -110.42

Call:
lm(formula = V ~ D + P, data = election.table)

Residuals:
Min        1Q    Median        3Q       Max
-0.101121 -0.036838 -0.006987  0.019029  0.163250

Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept)  0.514022   0.022793  22.552  1.2e-14 ***
D            0.043134   0.017381   2.482   0.0232 *
P           -0.006017   0.003891  -1.546   0.1394
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.06442 on 18 degrees of freedom
Multiple R-squared:  0.3372,	Adjusted R-squared:  0.2636
F-statistic: 4.579 on 2 and 18 DF,  p-value: 0.02468

We notice that although the full model we gave it had the interaction I:G, the function step never tried to use it. This is due to some rules implemented in step that do not include an interaction unless both main effects are already in the model. In this case, because neither $I$ nor $G$ were added, the interaction was never considered.

In the leaps example, we gave the function the design matrix and it did not have to consider interactions: they were already encoded in the design matrix.

### BIC example¶

The only difference between AIC and BIC is the price paid per variable. This is the argument k to step. By default k=2 and for BIC we set k=log(n). If we set k=0 it will always add variables.

In [9]:
%%R
election.step.forward.BIC = step(lm(V ~ 1, election.table),
list(upper = ~ I + D + W +G:I + P + N),
direction='forward', k=log(nrow(X)))
summary(election.step.forward.BIC)

Start:  AIC=-106.73
V ~ 1

Df Sum of Sq      RSS     AIC
+ D     1 0.0280805 0.084616 -109.71
<none>              0.112696 -106.73
+ I     1 0.0135288 0.099167 -106.38
+ P     1 0.0124463 0.100250 -106.15
+ N     1 0.0024246 0.110271 -104.15
+ W     1 0.0009518 0.111744 -103.87

Step:  AIC=-109.71
V ~ D

Df Sum of Sq      RSS     AIC
<none>              0.084616 -109.71
+ P     1 0.0099223 0.074693 -109.28
+ W     1 0.0068141 0.077801 -108.43
+ I     1 0.0012874 0.083328 -106.99
+ N     1 0.0000033 0.084612 -106.67

Call:
lm(formula = V ~ D, data = election.table)

Residuals:
Min        1Q    Median        3Q       Max
-0.125196 -0.033002 -0.007789  0.018511  0.150298

Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept)  0.48640    0.01466  33.172   <2e-16 ***
D            0.04509    0.01796   2.511   0.0212 *
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.06673 on 19 degrees of freedom
Multiple R-squared:  0.2492,	Adjusted R-squared:  0.2097
F-statistic: 6.305 on 1 and 19 DF,  p-value: 0.02124

### Backward selection¶

Just for fun, let's consider backwards stepwise. This starts at a full model and tries to delete variables.

There is also a direction="both" option.

In [10]:
%%R
election.step.backward = step(election.lm, direction='backward')
summary(election.step.backward)

Start:  AIC=-128.54
V ~ I + D + W + G:I + P + N

Df Sum of Sq      RSS     AIC
- P     1  0.000055 0.023741 -130.49
- W     1  0.000170 0.023855 -130.39
<none>              0.023686 -128.54
- N     1  0.003133 0.026818 -127.93
- D     1  0.011926 0.035612 -121.97
- I:G   1  0.050640 0.074325 -106.52

Step:  AIC=-130.49
V ~ I + D + W + N + I:G

Df Sum of Sq      RSS     AIC
- W     1  0.000120 0.023860 -132.38
<none>              0.023741 -130.49
- N     1  0.003281 0.027021 -129.77
- D     1  0.013983 0.037724 -122.76
- I:G   1  0.053507 0.077248 -107.71

Step:  AIC=-132.38
V ~ I + D + N + I:G

Df Sum of Sq      RSS     AIC
<none>              0.023860 -132.38
- N     1  0.003199 0.027059 -131.74
- D     1  0.013867 0.037727 -124.76
- I:G   1  0.059452 0.083312 -108.12

Call:
lm(formula = V ~ I + D + N + I:G, data = election.table)

Residuals:
Min        1Q    Median        3Q       Max
-0.043509 -0.019208 -0.004912  0.009626  0.090627

Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept)  0.506530   0.020689  24.483 4.15e-14 ***
I           -0.019417   0.014701  -1.321  0.20515
D            0.055436   0.018180   3.049  0.00765 **
N           -0.004653   0.003177  -1.465  0.16241
I:G          0.009588   0.001519   6.314 1.03e-05 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.03862 on 16 degrees of freedom
Multiple R-squared:  0.7883,	Adjusted R-squared:  0.7353
F-statistic: 14.89 on 4 and 16 DF,  p-value: 2.95e-05

## Cross-validation¶

Yet another model selection criterion is $K$-fold cross-validation.

• Fix a model ${\cal M}$. Break data set into $K$ approximately equal sized groups $(G_1, \dots, G_K)$.
• For (i in 1:K) Use all groups except $G_i$ to fit model, predict outcome in group $G_i$ based on this model $\widehat{Y}_{j,{\cal M}, G_i}, j \in G_i$.
• Similar to what we saw in Cook's distance which is $n$-fold cross validation.
• Estimate $CV({\cal M}) = \frac{1}{n}\sum_{i=1}^K \sum_{j \in G_i} (Y_j - \widehat{Y}_{j,{\cal M},G_i})^2.$

• It is a general principle that can be used in other situations to "choose parameters."
• Pros (partial list): "objective" measure of a model.
• Cons (partial list): inference is usually "out the window" (also true for other model selection procedures).
• If goal is not really inference about certain specific parameters, it is a reasonable way to compare models.

### $C_p$ versus 5-fold cross-validation¶

Let's plot our $C_p$ versus the $CV$ score. Keep in mind that there is additional randomness in the $CV$ score due to the random assignments to groups. Below, I have set the random seed so the results stay the same each time I run this chunk of code.

In [12]:
%%R
plot(election.leaps$Cp, election.leaps$CV, pch=23, bg='orange', cex=2)

In [13]:
%%R
plot(election.leaps$size, election.leaps$CV, pch=23, bg='orange', cex=2)
best.model.Cv = election.leaps$which[which((election.leaps$CV == min(election.leaps$CV))),] best.model.Cv   1 2 3 4 5 6 FALSE TRUE FALSE TRUE TRUE TRUE  ### Conclusions¶ The model selected depends on the criterion used. Criterion Model$R^2$~$ I + D + W +G:I + P + NR^2_a$~$ I + D + P + NC_p$~$D+P+N$AIC forward ~$D+P$BIC forward ~$D$AIC backward ~$I + D + N + I:G$5-fold CV ~$ I+W$The selected model is random! ## Where we are so far¶ • Many other "criteria" have been proposed. • Some work well for some types of data, others for different data. • Check diagnostics! • These criteria (except cross-validation) are not "direct measures" of predictive power, though Mallow’s$C_p$is a step in this direction. •$C_p$measures the quality of a model based on both bias and variance of the model. Why is this important? • Bias-variance tradeoff is ubiquitous in statistics. More next class. ## Inference after selection¶ Each of the above criteria return a model. The summary provides$p$-values. In [14]: %%R summary(election.step.forward)  Call: lm(formula = V ~ D + P, data = election.table) Residuals: Min 1Q Median 3Q Max -0.101121 -0.036838 -0.006987 0.019029 0.163250 Coefficients: Estimate Std. Error t value Pr(>|t|) (Intercept) 0.514022 0.022793 22.552 1.2e-14 *** D 0.043134 0.017381 2.482 0.0232 * P -0.006017 0.003891 -1.546 0.1394 --- Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1 Residual standard error: 0.06442 on 18 degrees of freedom Multiple R-squared: 0.3372, Adjusted R-squared: 0.2636 F-statistic: 4.579 on 2 and 18 DF, p-value: 0.02468  We can also form confidence intervals. But, can we trust these intervals or tests! In [15]: %%R confint(election.step.forward)   2.5 % 97.5 % (Intercept) 0.466136288 0.561907650 D 0.006618001 0.079649847 P -0.014193177 0.002158189  ### LARS: a variant of forward stepwise¶ To illustrate the "dangers" of trusting the above$p$-values, I will use the lars package which we will see later. This algorithm adds variables to a model one at a time as does forward stepwise. The algorithm can be viewed as a modification of forward stepwise, sometimes called a more democratic version of forward stepwise. In [16]: %%R library(lars) plot(lars(X, V, type='lar'))  Loaded lars 1.2  The path can be parameterized by a positive parameter called$\lambda$. The first value$\lambda_1$is, up to some multiplicative factor, the largest correlation of any columns of$X$with$Y$. In this sense, the first step of LARS and forward stepwise are the same. In [17]: %%R nsim = 5000 exactP = c() naiveP = c() for (i in 1:nsim) { Z = rnorm(nrow(X)) L0 = lars(X, Z, type='lar', max.steps=3) lam1 = L0$lambda[1]
lam2 = L0$lambda[2] naiveP = c(naiveP, 2 * (1 - pnorm(lam1))) exactP = c(exactP, (1 - pnorm(lam1)) / (1 - pnorm(lam2))) }  In [18]: %%R plot(ecdf(naiveP), lwd=3, col='red') abline(0,1, lwd=2, lty=2)  What is the type I error of the first test? In [19]: %%R ecdf(naiveP)(0.05)  [1] 0.2296  It turns out that it is possible to modify the usual$t\$-statistic so that we still get valid tests after the first step. This is what I called exactP above.

In [20]:
%%R
plot(ecdf(exactP), lwd=3, col='blue')
abline(0,1, lwd=2, lty=2)

### An exciting area of research¶

This exactP was only discovered recently!

For at least 10 years, I have been saying things along the lines of

Inference after model selection is basically out the window.
Forget all we taught you about t and F distributions as it
is no longer true...

It turns out that inference after selection is possible, and it doesn't force us to throw away all of our tools for inference.

But, it is a little more complicated to describe.


text:
# A container has a volume of 24 L and holds 32 mol of gas. If the container is compressed such that its new volume is 14 L, how many moles of gas must be released from the container to maintain a constant temperature and pressure?

Apr 28, 2017

The number of moles to be released is $= 13.3 m o l$

#### Explanation:

${V}_{1} / {n}_{1} = {V}_{2} / {n}_{2}$

Initial volume is ${V}_{1} = 24 L$

Final volume is ${V}_{2} = 14 L$

Initial number of moles is ${n}_{1} = 32 m o l$

Final number of moles is

${n}_{2} = {V}_{2} / {V}_{1} \cdot {n}_{1} = \frac{14}{24} \cdot 32 = 18.7 m o l$

Number of moles to be released is $= 32 - 18.7 = 13.3 m o l$

format: plain


text:
Can I reconstruct the cohomology from a collection of open sets?

Suppose I have a topological space $$X$$ with a collection of closed subsets $$X_\tau$$ for $$\tau \in P$$ where I think of $$P$$ as a poset with $$\tau \leq \lambda \iff X_\tau \subset X_\lambda$$. Is there some nice (algorithmic?) way to get information about the (compactly supported) cohomology of $$U_{\tau} = X_\tau - \bigcup_{\lambda<\tau}X_\lambda$$ in terms of the cohomology of the $$X_\tau$$?

For instance, if we I just one closed subset $$Z \subset X$$, then there is a long exact sequence: $$\dots \to H^n_c(U) \to H^n_c(X) \to H^n_c(Z) \to \dots$$ Is there something similar in the general case? I can certainly think of some inductive process for building up the relevant cohomology starting from the lowest strata by a combination of the excision sequence and Mayer-Vietoris but it would be nice if there was succinct description.

• Is $P$ the collection of all closed subsets or just some poset? To recover cohomology you need much more than just the collection of cohomologies, but also induced homomorphisms. Jul 29 at 23:04
• $P$ is just some poset (that I know a lot about). Let's say I know the induced homomorphisms too. Jul 29 at 23:08
• I think you can obtain a spectral sequence where the first term is the cohomology of $X_\tau$, the second term is the sum over all (let's say) maximal $\lambda < \tau$ of the cohomology of $X_\lambda$, the third is the sum over all pairs of maximal $\lambda_1,\lambda_2<\tau$ of the cohomology of $X_{\lambda_1} \cap X_{\lambda_2}$, and so on. (All these cohomologies are compactly supported). Whether that's computable depends a lot on your spaces and maps... Jul 30 at 0:28
• @WillSawin That's along the lines of what I am imagining too. Do you have any references in mind where this might have been worked out or an example along these lines might have occurred? Jul 30 at 1:02
• Your example may be a special case of the theory of hypercoverings as in Deligne's construction of mixed Hodge theory (or other works you can find by searching around, e.g. Brian Conrad's notes on cohomological descent math.stanford.edu/~conrad/papers/hypercover.pdf). The proof I would thin of would be to write down an explicit long exact sequence of sheaves starting with the constant sheaf on $X_\tau$, then the sum of the constant sheaves on $X_\lambda$, etc., then view it as a filtration of an object in the derived category of sheaves and take the spectral sequence of a filtration. Jul 30 at 1:10

I wrote a paper on precisely this question:

A spectral sequence for stratified spaces and configuration spaces of points. Geom. Topol. 21 (2017), no. 4, 2527–2555.

• Perfect, thanks! Jul 30 at 18:28

I am still unsure about your assumptions on $$P$$ and on the amount of information that you have. Here is a silly example:

Let $$X=X_\tau$$ be, say, $${\mathbb R}^n$$ and take the posets $$P=\{X, \{x\}\}$$, $$Q=\{X, \{x\}, \{y\}\}$$, where $$x\ne y$$ are points in $$X$$. Then, of course, $$H^*_c(X\setminus \{x,y\})$$ is not isomorphic to $$H^*_c(X\setminus \{x\})$$, even though you have the same data in terms of induced homomorphisms $$H^*_c(X)\to H^*_c(X_\nu),$$ for $$X_\nu \in P$$ and for $$X_\nu \in Q$$.

As Will suggested, if you have much more data in terms of the boolean algebra generated by $$P$$ and the corresponding induced homomorphisms, then you can build a spectral sequence.

• In my case, the $X_\tau$ will just be projective spaces of varying dimensions. I also suspect that there should be spectral sequence formulation. Do you have a reference for where I can read about this or even where an example is done of this kind so I don't have to reinvent the wheel? Jul 30 at 1:01
• If I understand your example right, doesn't it fall under the excision exact sequence category? I am happy getting partial information about my cohomology groups if that's what you mean. Jul 30 at 1:04


text:
# Counting in N-Dimensions

Notes:

Using the Eclipse IDE, I have created a Java project that implements what is discussed in this post. You can view or download it from my github repository.

For convenience, this article includes the number 0 in the set of natural numbers, $\mathbb{N}$, which by convention usually does not include the number 0.

Definition: A set S is a countable set if and only if there exists a bijective mapping $f: S \to \mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers
(i.e. for any pair of elements, a and b in S for which a $\neq$ b, $f(a) \neq f(b)$, and for any element, n in $\mathbb{N}$, there exists an element c in S, such that $f(c) = n$).

$\begin{array}{c |ccccc} \mathbb{N}^2 & 0 & 1 & 2 & 3 & \dots \\ \hline 0 & (0,0) & (0,1) & (0,2) & (0,3) \\ 1 & (1,0) & (1,1) & (1,2) & (1,3) \\ 2 & (2,0) & (2,1) & (2,2) & (2,3) \\ 3 & (3,0) & (3,1) & (3,2) & (3,3) \\ \vdots & & & & & \ddots \end{array}$

By creating a table with rows and columns both labeled by the natural numbers in ascending order, and with entries consisting of these ordered row and height number pairs, each entry can be counted while traversing along the diagonals of the table in such a manner as to yield the following sequence listing the elements of $\mathbb{N}^2$:

$\mathbb{N}^2 = \{(0,0), (1,0), (0,1),(2,0),(1,1),(0,2),(3,0),(2,1), ...\}$

The reason for traversing along the diagonals of the table instead of its rows or columns is that, although they grow larger as the process continues, the diagonals are always finite in length. If I needed to count up to a particular ordered pair, I could always reach it in a finite number of steps by counting along the table’s diagonals. On the other hand, the rows and columns of the table are infinite in length. Were I to count along them, I could never get to an element occurring in a subsequent row or column.

Clearly, every possible ordered pair of natural numbers occurs in this sequence exactly once. Since there are an infinite number of possible ordered pairs of natural numbers, the sequence must be infinite in length. In this way, the set $\mathbb{N}^2$ satisfies the definition of a countable set (a similar argument demonstrates that $\mathbb{Q}$, the set of rational numbers, is also a countable set).

Repeating this process, the elements of $\mathbb{N}^{3}$ can be counted by constructing a table with rows in $\mathbb{N}$ and with columns in $\mathbb{N}^{2}$

$\begin{array}{c |ccccc} \mathbb{N}^3 & \mathbb{N}^2_{0} & \mathbb{N}^2_{1} & \mathbb{N}^2_{2} & \mathbb{N}^2_{3} & \dots \\ \hline 0 & (0,\mathbb{N}^2_{0}) & (0,\mathbb{N}^2_{1}) & (0,\mathbb{N}^2_{2}) & (0,\mathbb{N}^2_{3}) \\ 1 & (1,\mathbb{N}^2_{0}) & (1,\mathbb{N}^2_{1}) & (1,\mathbb{N}^2_{2}) & (1,\mathbb{N}^2_{3}) \\ 2 & (2,\mathbb{N}^2_{0}) & (2,\mathbb{N}^2_{1}) & (2,\mathbb{N}^2_{2}) & (2,\mathbb{N}^2_{3}) \\ 3 & (3,\mathbb{N}^2_{0}) & (3,\mathbb{N}^2_{1}) & (3,\mathbb{N}^2_{2}) & (3,\mathbb{N}^2_{3}) \\ \vdots & & & & & \ddots \end{array} = \begin{array}{c |ccccc} \mathbb{N}^3 & (0,0) & (1,0) & (0,1) & (2,0) & \dots \\ \hline 0 & (0,0,0) & (0,1,0) & (0,0,1) & (0,2,0) \\ 1 & (1,0,0) & (1,1,0) & (1,0,1) & (1,2,0) \\ 2 & (2,0,0) & (2,1,0) & (2,0,1) & (2,2,0) \\ 3 & (3,0,0) & (3,1,0) & (3,0,1) & (3,2,0) \\ \vdots & & & & & \ddots \end{array}$

which gives the sequence of elements in $\mathbb{N}^3$:

$\mathbb{N}^3 = \{(0,0,0), (1,0,0), (0,1,0),(2,0,0),(1,1,0),(0,0,1),(3,0,0),(2,1,0), ...\}$

This sequence can in turn be crossed with $\mathbb{N}$ once more to count the elements of $\mathbb{N}^{4}$, and so on.

If I am given a particular n-tuple, can I find its sequence index number without counting up to it? For instance, at what index in $\mathbb{N}^3$ does the 3-tuple (13, 5, 7) occur? Obversely, if I am given a particular index number, can I find its corresponding n-tuple? for instance what is the 47th element in the $\mathbb{N}^5$ sequence?

It is best to first solve the simplest case in $\mathbb{N}^2$, and then generalize to $\mathbb{N}^p$

As elements in $\mathbb{N}^2$ are two-dimensional, this suggests a function of two variables, $f: \mathbb{N}\times\mathbb{N} \to \mathbb{N}$. As it turns out, it suffices that $f$ be quadratic.

Thus, with as yet unknown constants $C_i$,

$f(x,y) = C_0 x^2 + C_1 y^2 + C_2 xy + C_3 x + C_4 y + C_5$

As there are six unknown constants, a system of six equations suffices to determine what they are. We know that (0,0) is the zeroth element in $\mathbb{N}^2$, (1,0) is the 1st element, (0,1) is the 2nd, and so on…

$\begin{array}{c} f(0,2) = C_0 (0)^2 + C_1 (2)^2 + C_2 (0)(2) + C_3 (0) + C_4 (2) + C_5 = 5 \\ f(1,1) = C_0 (1)^2 + C_1 (1)^2 + C_2 (1)(1) + C_3 (1) + C_4 (1) + C_5 = 4 \\ f(2,0) = C_0 (2)^2 + C_1 (0)^2 + C_2 (2)(0) + C_3 (2) + C_4 (0) + C_5 = 3 \\ f(0,1) = C_0 (0)^2 + C_1 (1)^2 + C_2 (0)(1) + C_3 (0) + C_4 (1) + C_5 = 2 \\ f(1,0) = C_0 (1)^2 + C_1 (0)^2 + C_2 (1)(0) + C_3 (1) + C_4 (0) + C_5 = 1 \\ f(0,0) = C_0 (0)^2 + C_1 (0)^2 + C_2 (0)(0) + C_3 (0) + C_4 (0) + C_5 = 0 \\ \end{array}$

Solving the system,

$\begin{bmatrix}0&4&0&0&2&1\\ 1&1&1&1&1&1\\ 4&0&0&2&0&1\\ 0&1&0&0&1&1\\ 1&0&0&1&0&1\\ 0&0&0&0&0&1 \end{bmatrix} \begin{bmatrix}C_0\\C_1\\C_2\\C_3\\C_4\\C_5\end{bmatrix} = \begin{bmatrix}5\\4\\3\\2\\1\\0\end{bmatrix}$

gives $C_0 = \frac{1}{2}, C_1 = \frac{1}{2}, C_2 = 1, C_3 = \frac{1}{2}, C_4 = \frac{3}{2}, C_5 = 0.$

and so,

\begin{aligned} f(x,y) &= \frac{1}{2}x^2 + \frac{1}{2}y^2 + xy + \frac{1}{2}x + \frac{3}{2}y \\ &= \frac{1}{2}(x+y)(x+y+1)+y \end{aligned}

This is known as the Cantor pairing function.

Not only can this function give the index of a particular 2-tuple, but by composing it recursively, it can give the index of a general n-tuple.

$f(x_1,x_2,...,x_n) = f(x_1,f(x_2,f(...,f(x_{n-1},x_n)))$

Now I can find the index of (13, 5, 7) in $\mathbb{N}^3$:

\begin{aligned} f(13,5,7) &= f(13,f(5,7)) \\ &= f(13, \frac{1}{2}(5+7)(5+7+1)+7) \\ &= f(13,85) \\ &= \frac{1}{2}(13+85)(13+85+1)+85 \\ &= 4,936 \end{aligned}

What about the inverse of this function, $f^{-1}: \mathbb{N} \to \mathbb{N}^p$? Given an index, can I calculate its corresponding n-tuple?

I will first show how to begin with a particular index in $\mathbb{N}^2$, i, and find the 2-tuple, (x(i),y(i)), that it corresponds to. Observe that the first element of the nth diagonal always begins with (n,0). Now also observe that the nth diagonal of the $\mathbb{N}^2$ table has n+1 elements. For instance, the 0th diagonal has one element, the 1st diagonal has 2 elements, the 2nd diagonal has 3 elements, and so on. This suggests the following mappings:

$\begin{array}{ccccc} f^{-1}(0) & = & f^{-1}(0) & = & (0,0) \\ f^{-1}(0+1) & = & f^{-1}(1) & = & (1,0) \\ f^{-1}(0+1+2) & = & f^{-1}(3) & = & (2,0) \\ f^{-1}(0+1+2+3) & = & f^{-1}(6) & = & (3,0) \\ \vdots & & \vdots & & \vdots \\ f^{-1}(0+1+2+3+...+n) & = & f^{-1}(\frac{n(n+1)}{2}) & = & (n,0) \\ \end{array}$

If the ith element is also the $\frac{n(n+1)}{2}$th element, for some n, then

$\begin{array}{c} i = \frac{n(n+1)}{2} \\ \to 0 = n^2 + n - 2i \\ \to n = \frac{ \sqrt{1+8i}-1 }{2} \\ \end{array}$

If i is larger than the $\frac{n(n+1)}{2}$th element, but still in the same diagonal, and hence, at most the $\frac{n(n+1)}{2} + n$th element

$\lfloor\frac{\sqrt{1+8i}-1}{2}\rfloor < n$

I can find the x(i) coordinate by substituting for n, this expression into $\frac{n(n+1)}{2} + n - i= \frac{n(n+3)}{2} - i$. The y(i) coordinate is derived similarly.

\begin{aligned} x(i) &= \frac{\lfloor\frac{\sqrt{1+8i}-1}{2}\rfloor(\lfloor\frac{\sqrt{1+8i}-1}{2}\rfloor+3)}{2} - i \\ y(i) &= i - \frac{\lfloor\frac{\sqrt{1+8i}-1}{2}\rfloor(\lfloor\frac{\sqrt{1+8i}-1}{2}\rfloor+1)}{2}\end{aligned}

I can extend the use of these equations to n-tuples by composing them in the following manner.

\begin{aligned} \mathbb{N}^q_{i} &= \mathbb{N}_{x(i)}\times\mathbb{N}^{q-1}_{y(i)} \\ &=\mathbb{N}_{x(i)}\times\mathbb{N}_{x(y(i))}\times\mathbb{N}^{q-2}_{y(y(i))} \\ &=\mathbb{N}_{x(i)}\times\mathbb{N}_{x(y(i))}\times\mathbb{N}_{x(y(y(i)))}\times\mathbb{N}^{q-3}_{y(y(y(i)))} \\ &= \dots \end{aligned}

Now I can answer the second question, what is the 47th element in the $\mathbb{N}^5$ sequence?

\begin{aligned} \mathbb{N}^5_{47} &= (\mathbb{N}_{x(47)},\mathbb{N}^{4}_{y(47)}) \\ &=(7,\mathbb{N}^{4}_{2}) \\ &=(7,\mathbb{N}_{x(2)},\mathbb{N}^{3}_{y(2)}) \\ &=(7,0,\mathbb{N}^{3}_{1}) \\ &=(7,0,1, \mathbb{N}^{2}_{0}) \\ &=(7,0,1, \mathbb{N}_{x(0)}, \mathbb{N}_{y(0)}) \\ &=(7,0,1, 0, 0) \end{aligned}

I have created a Java class, RecursiveIntTupleGenerator, that generates these sequences. An instance of this class has a specified number of dimensions, and is initialized to the 0th element of its corresponding sequence. You can view/download the Eclipse project source here.

$\begin{tabular}{|l|} \hline RecursiveIntTupleGenerator \\ \hline -x: int \\ -subTuple: RecursiveIntTupleGenerator \\ -savedX: int \\ -dimensions: int \\ \hline +constructor(int numDimensions) \\ +getDimensions() \\ +getVal(int index) \\ +setZero() \\ +next() \\ +toString() \\ ... \\ \hline\end{tabular}$

As discussed above, the Cantor pairing function directly associates the natural numbers to the respective natural number n-tuple, and vice versa, but I was also interested in capturing the recursive nature of the n-tuple counting process. This is implemented in the next() method.

	public void next() {
if (dimensions == 1) {
x += 1;
} else {
if (x > 0) {
x -= 1;
subTuple.next();
} else {
savedX += 1;
x = savedX;
subTuple.setZero();
}
}
}

I’d like to expand on this project in the future. It must be possible to iterate over the integers (including negative numbers) in multiple dimensions just as well as it is possible to iterate over the natural numbers. Also, since this procedure may theoretically carry on indefinitely, it would make more sense to use Java’s BigInteger class instead of just integers.

Being able to generate a sequence of every possible positive whole number n-tuple affords an easy, brute-force solution search for multivariate Diophantine equations, and various other problems in number theory. I put my Java class to the test and verified Lagrange’s four-square theorem for the first 100 whole numbers.

$\begin{array}{c} 0 = 0^{2} + 0^{2} + 0^{2} + 0^{2} \\ 1 = 1^{2} + 0^{2} + 0^{2} + 0^{2} \\ 2 = 1^{2} + 1^{2} + 0^{2} + 0^{2} \\ 3 = 1^{2} + 1^{2} + 1^{2} + 0^{2} \\ 4 = 2^{2} + 0^{2} + 0^{2} + 0^{2} \\ 5 = 2^{2} + 1^{2} + 0^{2} + 0^{2} \\ \vdots \\ 95 = 9^{2} + 3^{2} + 2^{2} + 1^{2} \\ 96 = 8^{2} + 4^{2} + 4^{2} + 0^{2} \\ 97 = 9^{2} + 4^{2} + 0^{2} + 0^{2} \\ 98 = 9^{2} + 4^{2} + 1^{2} + 0^{2} \\ 99 = 7^{2} + 7^{2} + 1^{2} + 0^{2} \\ \end{array}$

I let my program run longer and verified the theorem for numbers up to 5,000. My program took a much, much longer time to verify the solution, $3,072 = 32^{2} + 32^{2} + 32^{2} + 0^{2}$  than it did for any other number in this range. It must take many calls of the next() function to find this solution. Starting from (0,0,0,0), how many times does the next() function have to be called in order to find these four squares that add up to 3,072?

Advertisements


text:
## The Summer 2017 Mathematics A To Z: Well-Ordering Principle

It’s the last full week of the Summer 2017 A To Z! Four more essays and I’ll have completed this project and curl up into a word coma. But I’m not there yet. Today’s request is another from Gaurish, who’s given me another delightful topic to write about. Gaurish hosts a fine blog, For the love of Mathematics, which I hope you’ve given a try.

# Well-Ordering Principle.

An old mathematics joke. Or paradox, if you prefer. What is the smallest whole number with no interesting properties?

Not one. That’s for sure. We could talk about one forever. It’s the first number we ever know. It’s the multiplicative identity. It divides into everything. It exists outside the realm of prime or composite numbers. It’s — all right, we don’t need to talk about one forever. Two? The smallest prime number. The smallest even number. The only even prime. The only — yeah, let’s move on. Three; the smallest odd prime number. Triangular number. One of only two prime numbers that isn’t one more or one less than a multiple of six. Let’s move on. Four. A square number. The smallest whole number that isn’t 1 or a prime. Five. Prime number. First sum of two different prime numbers. Part of the first prime pair. Six. Smallest perfect number. Smallest product of two different prime numbers. Let’s move on.

And so on. Somewhere around 22 or so, the imagination fails and we can’t think of anything not-boring about this number. So we’ve found the first number that hasn’t got any interesting properties! … Except that being the smallest boring number must be interesting. So we have to note that this is otherwise the smallest boring number except for that bit where it’s interesting. On to 23, which used to be the default funny number. 24. … Oh, carry on. Maybe around 31 things settle down again. Our first boring number! Except that, again, being the smallest boring number is interesting. We move on to 32, 33, 34. When we find one that couldn’t be interesting, we find that’s interesting. We’re left to conclude there is no such thing as a boring number.

This would be a nice thing to say for numbers that otherwise get no attention, if we pretend they can have hurt feelings. But we do have to admit, 1729 is actually only interesting because it’s a part of the legend of Srinivasa Ramanujan. Enjoy the silliness for a few paragraphs more.

(This is, if I’m not mistaken, a form of the heap paradox. Don’t remember that? Start with a heap of sand. Remove one grain; you’ve still got a heap of sand. Remove one grain again. Still a heap of sand. Remove another grain. Still a heap of sand. And yet if you did this enough you’d leave one or two grains, not a heap of sand. Where does that change?)

Another problem, something you might consider right after learning about fractions. What’s the smallest positive number? Not one-half, since one-third is smaller and still positive. Not one-third, since one-fourth is smaller and still positive. Not one-fourth, since one-fifth is smaller and still positive. Pick any number you like and there’s something smaller and still positive. This is a difference between the positive integers and the positive real numbers. (Or the positive rational numbers, if you prefer.) The thing positive integers have is obvious, but it is not a given.

The difference is that the positive integers are well-ordered, while the positive real numbers aren’t. Well-ordering we build on ordering. Ordering is exactly what you imagine it to be. Suppose you can say, for any two things in a set, which one is less than another. A set is well-ordered if whenever you have a non-empty subset you can pick out the smallest element. Smallest means exactly what you think, too.

The positive integers are well-ordered. And more. The way they’re set up, they have a property called the “well-ordering principle”. This means any non-empty set of positive integers has a smallest number in it.

This is one of those principles that seems so obvious and so basic that it can’t teach anything interesting. That it serves a role in some proofs, sure, that’s easy to imagine. But something important?

Look back to the joke/paradox I started with. It proves that every positive integer has to be interesting. Every number, including the ones we use every day. Including the ones that no one has ever used in any mathematics or physics or economics paper, and never will. We can avoid that paradox by attacking the vagueness of “interesting” as a word. Are you interested to know the 137th number you can write as the sum of cubes in two different ways? Before you say ‘yes’, consider whether you could name it ten days after you’ve heard the number.

(Granted, yes, it would be nice to know the 137th such number. But would you ever remember it? Would you trust that it’ll be on some Wikipedia page that somehow is never threatened with deletion for not being noteworthy? Be honest.)

But suppose we have some property that isn’t so mushy. Suppose that we can describe it in some way that’s indexed by the positive integers. Furthermore, suppose that we show that in any set of the positive integers it must be true for the smallest number in that set. What do we know?

— We know that it must be true for all the positive integers. There’s a smallest positive integer. The positive integers have this well-ordered principle. So any subset of the positive integers has some smallest member. And if we can show that something or other is always true for the smallest number in a subset of the positive integers, there you go.

This technique we call, when it’s introduced, induction. It’s usually a baffling subject because it’s usually taught like this: suppose the thing you want to show is indexed to the positive integers. Show that it’s true when the index is ‘1’. Show that if the thing is true for an arbitrary index ‘n’, then you know it’s true for ‘n + 1’. It’s baffling because that second part is hard to visualize. The student makes a lot of mistakes in learning, on examples of what the sum of the first ‘N’ whole numbers or their squares or cubes are. I don’t think induction is ever taught in this well-ordering principle method. But it does get used in proofs, once you get to the part of analysis where you don’t have to interact with actual specific numbers much anymore.

The well-ordering principle also gives us the method of infinite descent. You encountered this in learning proofs about, like, how the square root of two must be an irrational number. In this, you show that if something is true for some positive integer, then it must also be true for some other, smaller positive integer. And therefore some other, smaller positive integer again. And again, until you get into numbers small enough you can check by hand.

It keeps creeping in. The Fundamental Theorem of Arithmetic says that every positive whole number larger than one is a product of a unique string of prime numbers. (Well, the order of the primes doesn’t matter. 2 times 3 times 5 is the same number as 3 times 2 times 5, and so on.) The well-ordering principle guarantees you can factor numbers into a product of primes. Watch this slick argument.

Suppose you have a set of whole numbers that isn’t the product of prime numbers. There must, by the well-ordering principle, be some smallest number in that set. Call that number ‘n’. We know that ‘n’ can’t be prime, because if it were, then that would be its prime factorization. So it must be the product of at least two other numbers. Let’s suppose it’s two numbers. Call them ‘a’ and ‘b’. So, ‘n’ is equal to ‘a’ times ‘b’.

Well, ‘a’ and ‘b’ have to be less than ‘n’. So they’re smaller than the smallest number that isn’t a product of primes. So, ‘a’ is the product of some set of primes. And ‘b’ is the product of some set of primes. And so, ‘n’ has to equal the primes that factor ‘a’ times the primes that factor ‘b’. … Which is the prime factorization of ‘n’. So, ‘n’ can’t be in the set of numbers that don’t have prime factorizations. And so there can’t be any numbers that don’t have prime factorizations. It’s for the same reason we worked out there aren’t any numbers with nothing interesting to say about them.

And isn’t it delightful to find so simple a principle can prove such specific things?

## Words About A Wordless Induction Proof

This pair of tweets came across my feed. And who doesn’t like a good visual proof of a mathematical fact? I hope you enjoy.

So here’s the proposition.

This is the sort of identity we normally try proving by induction. Induction is a great scheme for proving identities like this. It works by finding some index on the formula. Then show that if the formula is true for one value of the index, then it’s true for the next-higher value of the index. Finally, find some value of the index for which it’s easy to check that the formula’s true. And that proves it’s true for all the values of that index above that base.

In this case the index is ‘n’. It’s really easy to prove the base case, since 13 is equal to 12 what with ‘1’ being the number everybody likes to raise to powers. Going from proving that if it’s true in one case — $1^3 + 2^3 + 3^3 + \cdots + n^3$ — then it’s true for the next — $1^3 + 2^3 + 3^3 + \cdots + n^3 + (n + 1)^3$ — is work. But you can get it done.

And then there’s this, done visually:

It took me a bit to read fully until I was confident in what it was showing. But it is all there.

As often happens with these wordless proofs you can ask whether it is properly speaking a proof. A proof is an argument and to be complete it has to contain every step needed to deduce the conclusion from the premises, following one of the rules of inference each step. Thing is basically no proof is complete that way, because it takes forever. We elide stuff that seems obvious, confident that if we had to we could fill in the intermediate steps. A wordless proof like trusts that if we try to describe what is in the picture then we are constructing the argument.

That’s surely enough of my words.

## Something Cute With 9’s and a 6.

After the last few essays I’d like to take a moment for a distinct, cute little problem of no practical use but cute.

Write down as many 9’s as you like, and when finished with that place a 6 at the right end. The result is divisible by 6.

That is, whatever number you’ve written, divided by 6, produces a whole number. Divisibility is one of those things which turns up whenever you have a collection of things which can be multiplied, and one thing is divisible by the second if you can find something in your collection so that the second multiplied by your find equals the first. It’s most often used to talk about the integers — the positive counting numbers, their negative counterparts, and zero if we didn’t include that already — and if it isn’t said divisible-with-respect-to-what then integers are what is usually meant. Partly that’s because integers are the first thing where divisibility stands out: if we look at the real numbers, everything is divisible by everything else (as long as that “else” is not zero), and a property that’s (almost) always true is usually too dull to mention. The next topic where divisibility gets mentioned much is usually polynomials, with a few eccentrics holding out for the complex numbers where the real part and the imaginary part are both integers.

There are several ways to prove this string of 9’s followed by 6 is divisible by 6. Here’s a proof which I like.


text:
# Frank solutions for Class 9 Maths ICSE chapter 3 - Compound Interest [Latest edition]

## Chapter 3: Compound Interest

Exercise 3.1Exercise 3.2
Exercise 3.1

### Frank solutions for Class 9 Maths ICSE Chapter 3 Compound Interest Exercise 3.1

Exercise 3.1 | Q 1.1

Find the amount and the compound interest payable annually on the following :

Rs.25000 for 1(1)/(2) years at 10% per annum.

Exercise 3.1 | Q 1.2

Find the amount and the compound interest payable annually on the following :

Rs.32000 for 2 years at 7(1)/(2)% per annum.

Exercise 3.1 | Q 1.3

Find the amount and the compound interest payable annually on the following :

Rs.10000 for 2(1)/(2) years at 6% per annum.

Exercise 3.1 | Q 1.4

Find the amount and the compound interest payable annually on the following :

Rs.24000 for 1(1)/(2) years at 7(1)/(2)% per annum.

[Hint : 1 year 146 days = 1(146)/(365)"year" = 1(2)/(5)"year"]

Exercise 3.1 | Q 2.1

Find the amount and the compound interest payable annually on:
Rs.16000 for 2 years at 15% and 12% for the successive years.

Exercise 3.1 | Q 2.2

Find the amount and the compound interest payable annually on:
Rs.17500 for 3 years at 8%, 10% and 12% for the successive years.

Exercise 3.1 | Q 3

Calculate the amount and compound interest on Rs 20000 for 3 years at 10% per annum, interest being payable annually.

Exercise 3.1 | Q 4

Compute the compound interest for the third year on Rs. 5000 invested for 5 years at 10% per annum, the interest being payable annually.

Exercise 3.1 | Q 5

Rakesh invests Rs.25600 at 5% per annum compound interest payable annually for 3 years. Find the amount standing to his credit at the end of the second year.

Exercise 3.1 | Q 6

Find the amount and compound interest on Rs.7500 for 1(1)/(2) years at 8%, payable semi-annually.

Exercise 3.1 | Q 7

A man invests Rs 24000 for two years at compound interest, If his money amounts to Rs 27600 after one year, find the amount at the end of second year.

Exercise 3.1 | Q 8

How much will Rs 14000 amounts to 2 years at compound interest, if the rates for the successive years be 5% and 8% respectively?

Exercise 3.1 | Q 9

Find the amount and the compound interest on Rs 17500 for 3 years, if the rates for successive years is 4%, 5% and 6% respectively, the interest is payable annually.

Exercise 3.1 | Q 10

A man borrows ₹ 4000 at 14% p.a., compound interest, being payable half-yearly. Find the amount he has to pay at the end of 1(1)/(2) years.

Exercise 3.1 | Q 11

Calculate the amount and compound interest to the nearest rupee on Rs 42000 for 2 years at 8% per annum, interest being payable half-yearly.

Exercise 3.1 | Q 12

A man lends Rs 15000 at 10.5% per annum C.I., interest reckoned yearly, and another man lends the same sum at 10% per annum, interest being reckoned half-yearly. Who is the gainer at the end of one year and by how much?

Exercise 3.1 | Q 13

Find the difference between the compound interest and simple interest on Rs 20,000 at 12% per annum for 3 years, the compound interest being payable annually.

Exercise 3.1 | Q 14

The simple interest on a certain sum of money at 4% p.a. for 2 years is Rs1500. What will be the compound interest on the same sum for the same time?

Exercise 3.1 | Q 15

Find the difference between simple and compound interest on Rs 5000 invested for 3 years at 6% p.a., interest payable yearly.

Exercise 3.1 | Q 16

Simple interest on a sum of money for 2 years at 4% is Rs 450. Find the compound interest at the same rate for 1 year if the interest is reckoned half-yearly.

Exercise 3.1 | Q 17

A man borrows Rs 62500 at 8% p.a., simple interest for 2 years. He immediately lends the money out at CI at the same rate and for same time. What is his gain at the end of 2 years?

Exercise 3.1 | Q 18

What sum will amount to Rs.10120 in 2 years at C.I. payable annually, if the rates are 10% and 15% for the successive years?

Exercise 3.1 | Q 19

Sunil borrows Rs.50,000 at 10% S.I. for 1(1)/(2) years. He immediately invests the entire amount for 1(1)/(2) years at 10% compounded annually. What is his gain at the end of the stipulated time, when he repays his loan?

Exercise 3.1 | Q 20

The value of a mobile depreciated by 5% per year during the first two years and 10% per year during the third year. Express the total depreciation of the value of the mobile in percent during the three years.

Exercise 3.1 | Q 21

A man borrows Rs.6500 at 10% per annum compound interest payable half-yearly. He repays Rs.2000 at the end of every six months. Calculate the amount outstanding at the end of the third payment. Give your answer to the nearest rupee.

Exercise 3.1 | Q 22

A man borrows Rs.20000 at 10% per annum compound interest payable annually. If he repays Rs.5000 at the end of the first year and Rs.10000 at the end of the second year; how much should he pay at the end of the third year in order to clear the account? Find the answer correct to the nearest rupee.

Exercise 3.1 | Q 23

Ankita bought a gold ring worth Rs.x. The value of the ring increased at 10% per year compounded annually, on which the appreciation for the first year plus the appreciation for the second year amounts to Rs.6300. Find the value of the ring.

Exercise 3.1 | Q 24

Priyanka lends Rs.15,500 at 10% for the first year, at 15% for the second year and at 20% for the third year. If the rates of interest are compounded yearly, find the difference between the compound interest of the second year and the third year.

Exercise 3.1 | Q 25

Samidha borrowed Rs.7500 from Shreya at 30% per annum compounded interest. After 2 years, Samidha gave Rs.10000 and a juicer to Shreya to clear the debt. Find the cost of the juicer.

Exercise 3.2

### Frank solutions for Class 9 Maths ICSE Chapter 3 Compound Interest Exercise 3.2

Exercise 3.2 | Q 1.1

Find the amount and the compound interest on the following:
Rs.8000 for 3years at 10% per annum compounded annually.

Exercise 3.2 | Q 1.2

Find the amount and the compound interest on the following :
Rs.15000 for 2years at 8% per annum compounded semi-annually.

Exercise 3.2 | Q 1.3

Find the amount and the compound interest on the following :
Rs.12000 for 1(1)/(2) years at 5% per annum compounded annually.

Exercise 3.2 | Q 1.4

Find the amount and the compound interest on the following :
Rs.25000 for 2 years at 6% per annum compounded semi-annually.

Exercise 3.2 | Q 1.5

Find the amount and the compound interest on the following :
Rs.16000 for 3 years at 10%, 8% and 6% for successive years.

Exercise 3.2 | Q 2

Find the amount and compounded interest on Rs.15000 in 2(1)/(2) years at 10% p.a. compounded annually.

Exercise 3.2 | Q 3

Find the amount on Rs 36000 in 2 years 15% p.a. compounded annually.

Exercise 3.2 | Q 4

Find the amount and compound interest on Rs.50000 on 1(1)/(2) years at 8% p.a. compounded half-yearly.

Exercise 3.2 | Q 5

How much will Rs 25000 amount to in 2 years at compound interest, if the rates for 1st and 2nd years be 4% and 5% p.a. respectively?

Exercise 3.2 | Q 6

Find compound interest on Rs 31250 for 3 years, if the rates of interest for 1st,2nd and 3rd years be 8%, 10% and 12% respectively.

Exercise 3.2 | Q 7

Calculate the rate percent when Rs 28000 amount to Rs 30870 in 2 years at compounded annually.

Exercise 3.2 | Q 8

In what time will Rs 15625 amount to Rs 17576 at 4% p.a. compound interest?

Exercise 3.2 | Q 9

In how many years will Rs 2000 amount to Rs 2662 at 10% p.a. compound interest?

Exercise 3.2 | Q 10

The simple interest on a certain sum for 3 years at 4% is Rs 600. Find the compound interest for the same sum at the same percent and in the same time.

Exercise 3.2 | Q 11

The compound interest payable annually on a certain sum for 2 years is Rs 40.80 and the simple interest is Rs 40. Find the sum and the rate percent.

Exercise 3.2 | Q 12

The difference between simple interest and compound interest compounded annually on a certain sum is Rs.448 for 2 years at 8 percent per annum. Find the sum.

Exercise 3.2 | Q 13

The difference between C.I. payable annually and S.I. on Rs.50,000 for two years is Rs.125 at the same rate of interest per annum. Find the rate of interest.

Exercise 3.2 | Q 14

What principal will amount to Rs.15729 in two years, if the rate of interest for successive years are 5% and 7% respectively, the interest is being compounded annually.

Exercise 3.2 | Q 15

At what rate percent will Rs.12000 yield Rs.13891.50 as compound interest in 3 years?

Exercise 3.2 | Q 16

A sum of Rs.16820 is to be divided between two girls A and B, 27 and 25 years old respectively, in such a way that, if their portions be invested at 5% per annum compound interest payable annually, they will receive equal amounts on reaching 40 years of age. What is the share of each in the original sum of money?

## Chapter 3: Compound Interest

Exercise 3.1Exercise 3.2

## Frank solutions for Class 9 Maths ICSE chapter 3 - Compound Interest

Frank solutions for Class 9 Maths ICSE chapter 3 (Compound Interest) include all questions with solution and detail explanation. This will clear students doubts about any question and improve application skills while preparing for board exams. The detailed, step-by-step solutions will help you understand the concepts better and clear your confusions, if any. Shaalaa.com has the CISCE Class 9 Maths ICSE solutions in a manner that help students grasp basic concepts better and faster.

Further, we at Shaalaa.com provide such solutions so that students can prepare for written exams. Frank textbook solutions can be a core help for self-study and acts as a perfect self-help guidance for students.

Concepts covered in Class 9 Maths ICSE chapter 3 Compound Interest are Concept of Compound Interest, Inverse Formula, Miscellaneous Problem, When the Interest is Compounded Half Yearly, When the Time is Not an Exact Number of Years and the Interest is Compounded Yearly, Use of Compound Interest in Computing Amount Over a Period of 2 Or 3-years.

Using Frank Class 9 solutions Compound Interest exercise by students are an easy way to prepare for the exams, as they involve solutions arranged chapter-wise also page wise. The questions involved in Frank Solutions are important questions that can be asked in the final exam. Maximum students of CISCE Class 9 prefer Frank Textbook Solutions to score more in exam.

Get the free view of chapter 3 Compound Interest Class 9 extra questions for Class 9 Maths ICSE and can use Shaalaa.com to keep it handy for your exam preparation


text:
News

# $89 Million in DOE Funding Announced for Energy-Related Manufacturing Technologies May 09, 2019 by Scott McMahan Energy Secretary Rick Perry announced that the U.S. Department of Energy is offering$89 million in funding to support innovative, advanced manufacturing research and development projects. This Funding Opportunity Announcement (FOA) is intended to fund key departmental priorities including domestic manufacturing for energy storage. (image above ID 130901084 © Leowolfert | Dreamstime.com).

The United States' manufacturing sector is booming. U.S. manufacturers have created almost 500,000 jobs since 2017 and more than 250,000 jobs in the last year alone.

However, the manufacturing sector also uses about 25% of the nation's energy.

"Embracing new technologies that drive innovation in American manufacturing is the key to creating real-world progress that significantly improves energy efficiency in manufacturing," said U.S. Secretary of Energy Rick Perry. "By focusing on energy-related advanced manufacturing technologies, we are building a new era of manufacturing that will stimulate the economy, create jobs and build American energy independence."

The FOA seeks proposals in three areas that will improve the global competitiveness of the U.S. by driving innovation related to the manufacturing of key energy technologies and by reducing industrial process energy consumption.

#### Topic 1-Innovations for the Manufacture of Advanced Materials

Topic 1 focuses on employing machine learning to develop better batteries, phase change storage materials for heating and cooling applications, and new semiconductors that convert temperature differences into electricity. A primary goal is developing and scaling new, low-cost manufacturing processes to mobilize increased domestic battery manufacturing for vehicle and stationary applications.

#### Topic 2-Lower Thermal Budget Processes for Industrial Efficiency & Productivity

With 70% of all process energy use related to heating, this topic targets novel research about industrial process drying technologies that increase energy efficiency throughput and product quality. It also seeks new ideas on the use of process intensification to reduce overall heating energy.

#### Topic 3-Connected, Flexible and Efficient Manufacturing Facilities and Energy Systems

With advances in new, wide-bandgap semiconductors supported by DOE, this topic investigates the application of more efficient industrial power conversion equipment and explores new opportunities for converting process energy to electrical energy and better integrating it with the electrical grid. It also seeks proposals for advancements in combined heat and power that result in higher electrical efficiencies.

The DOE Office of Energy Efficiency and Renewable Energy's Advanced Manufacturing Office will lead this initiative. DOE anticipates proffering up to 55 awards for up to three years. A cost-share of at least 20% will be required for research and development projects.

View the funding application and submission requirements HERE. Concept papers are due on June 20, 2019.

This FOA follows Secretary Perry's March 26, 2019 announcement calling for proposals to address cybersecurity for energy efficient manufacturing. Up to \$70 million, subject to appropriations, is available for the Clean Energy Manufacturing Innovation Institute to address cyber-security issues related to energy efficient manufacturing. Concept papers are due May 15, 2019.


text:
Vernier Software & Technology

# Energy Content of Fuels

## Introduction

In this experiment, you will find and compare the heat of combustion of two different fuels: paraffin wax and ethanol. Paraffin is a member of a group of compounds called alkanes that are composed entirely of carbon and hydrogen atoms. Many alkanes, such as gasoline and diesel oil, are important fuels. Ethanol, C2H5OH, is used as a gasoline additive (gasohol) and as a gasoline substitute. In this experiment, you will compare the energy content of paraffin and ethanol by measuring their heats of combustion in kJ/g of fuel.

In order to find the heat of combustion, you will first use the energy from burning ethanol or paraffin to heat a known quantity of water. By monitoring the temperature of the water, you can find the amount of heat transferred to it, using the formula

$q = C_p \cdot m \cdot \Delta t$

where q is heat, Cp is the specific heat capacity of water, m is the mass of water, and Δt is the change in temperature of the water. Finally, the amount of fuel burned will be taken into account by calculating the heat per gram of fuel consumed in the combustion.

## Objectives

In this experiment, you will

• Compare the heat of combustion for paraffin wax and ethanol.
• Calculate the heat of combustion and percent efficiency for both fuels.

## Sensors and Equipment

This experiment features the following Vernier sensors and equipment.

### Option 2

You may also need an interface and software for data collection. What do I need for data collection?

## Chemistry with Vernier

See other experiments from the lab book.

 1 Endothermic and Exothermic Reactions 2 Freezing and Melting of Water 3 Another Look at Freezing Temperature 4 Heat of Fusion of Ice 5 Find the Relationship: An Exercise in Graphing Analysis 6 Boyle's Law: Pressure-Volume Relationship in Gases 7 Pressure-Temperature Relationship in Gases 8 Fractional Distillation 9 Evaporation and Intermolecular Attractions 10 Vapor Pressure of Liquids 11 Determining the Concentration of a Solution: Beer's Law 12 Effect of Temperature on Solubility of a Salt 13 Properties of Solutions: Electrolytes and Non-Electrolytes 14 Conductivity of Solutions: The Effect of Concentration 15 Using Freezing Point Depression to Find Molecular Weight 16 Energy Content of Foods 17 Energy Content of Fuels 18 Additivity of Heats of Reaction: Hess's Law 19 Heat of Combustion: Magnesium 20 Chemical Equilibrium: Finding a Constant, Kc 21 Household Acids and Bases 22 Acid Rain 23 Titration Curves of Strong and Weak Acids and Bases 24 Acid-Base Titration 25 Titration of a Diprotic Acid: Identifying an Unknown 26 Using Conductivity to Find an Equivalence Point 27 Acid Dissociation Constant, Ka 28 Establishing a Table of Reduction Potentials: Micro-Voltaic Cells 29 Lead Storage Batteries 30 Rate Law Determination of the Crystal Violet Reaction 31 Time-Release Vitamin C Tablets 32 The Buffer in Lemonade 33 Determining the Free Chlorine Content of Swimming Pool Water 34 Determining the Quantity of Iron in a Vitamin Tablet 35 Determining the Phosphoric Acid Content in Soft Drinks 36 Microscale Acid-Base Titration

### Experiment 17 from Chemistry with Vernier Lab Book

#### Included in the Lab Book

Vernier lab books include word-processing files of the student instructions, essential teacher information, suggested answers, sample data and graphs, and more.